문제 설명
병천 유치원 유관순반에서는 다음 주에 독립기년관으로 소풍을 갑니다. 상진 선생님은 소풍 때 학생을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에 항상 서로 친구인 학생끼리만 짝을 지어 줘야 합니다.
상진 선생님은 학생에 대한 친구 정보가 주어질 때, 학생을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 만들고 싶습니다.
짝이 되는 학생이 일부만 다르더라도 다른 방법입니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.
(피카추, 이상해) (피아리, 꼬부기) (이브이, 푸린)
(피카추, 이상해) (피아리, 이브이) (꼬부기, 푸린)
https://www.algospot.com/judge/problem/read/PICNIC
입력 설명
첫 줄에는 테스트케이스의 수 T(1<=T<=50)이 주어집니다. 각 테스트케이스의 첫 줄에는 학생의 수 N(2<=N<=10)과 친구 정보의 수 M(0<=M<=N*(N-1)/2)이 주어집니다. 여기서 N은 짝수입니다. 각 테스트케이스의 두 번째 줄에는 M개의 정수 쌍이 주어집니다. 이 정수 쌍의 각 정수값은 학생 번호에 해당하며, 학생 번호는 0부터 N-1 사이의 정수입니다. 같은 정보가 입력에 두 번 주어지지 않습니다.
출력 설명
각 테스트케이스마다 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.
3
2 1
0 1
4 6
0 1 1 2 2 3 3 0 0 2 1 3
6 10
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5