소풍(PICNIC)

[dhjeon1993]

제목

소풍 (PICNIC)

알고리즘

완전탐색

문제 설명

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어야 합니다.
각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝 지을 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두가지 방법은 서로 다른 방법입니다.

• (태연, 제시카) (써니, 티파니) (효연, 유리)
• (태연, 제시카) (써니, 유리) (효연, 티파니)

제한 조건

• 프로그램은 1초 내에 실행되어야 합니다.
• 64MB 이하의 메모리만을 사용해야 합니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n(2 <= n <= 10)과 친구 쌍의 수 m(0 <= m <= n(n-1)/2)이 주어집니다. 그 다음 줄에 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

출력

1
3
4

설명

• 첫 번째 입력(2 1)에는 두 학생밖에 없으며 이들은 서로 친구입니다. 따라서 딱 한가지의 경우가 있게 되죠.
• 두 번째 입력(4 6)에는 네 명의 학생이 모두 서로 친구입니다. 이들을 보라돌이, 뚜비, 나나, 뽀라고 할 때 다음과 같은 세 가지의 방법이 있습니다.
  • (보라돌이, 뚜비)(나나, 뽀)
  • (뚜비, 뽀)(보라돌이, 나나)
  • (나나, 뚜비)(뽀, 보라돌이)