체스 대회

동네에서 큰 체스 대회가 열려 구경하러 갔다. 선수가 각각 $n$명인 두 팀 A와 B가 맞붙고, A팀의 모든 선수는 B팀의 모든 선수와 한 번씩 대국한다. 승수가 더 많은 팀이 우승한다. 비긴 대국에서는 두 선수가 $1/2$점씩 나눠 가진다.

어느 선수가 어느 팀인지는 모르지만, 대회 기간에 치러진 대국은 하나도 빠짐없이 적어 두었다. 문제는 일부 선수가 연습 삼아, 또는 재미로 일정에 없는 대국까지 했다는 점이다. 같은 팀 선수와 둔 대국도 있고, 이미 만난 상대 팀 선수와 한 번 더 둔 대국도 있다. 이 기록만으로 선수가 어느 팀 소속인지 가려낼 수 있을까?

기록과 어긋나지 않는 팀 배정을 세어라. 즉 서로 다른 팀에 속한 모든 선수 쌍이 기록에 적어도 한 번 나오는 배정을 세면 된다. 두 팀에는 이름이 없으므로 A와 B를 맞바꾼 배정은 같은 배정으로 본다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 100$). 각 테스트 케이스는 다음과 같이 주어진다.

• 첫 줄에 한 팀의 선수 수 $N$과 기록된 대국 수 $M$이 공백을 두고 주어진다 ($1 \le N \le 250$, $N^2 \le M \le 10^6$).
• 이어지는 $M$개 줄에 서로 다른 두 정수 $A$와 $B$가 공백을 두고 주어진다 ($1 \le A < B \le 2N$). 선수 $A$와 선수 $B$가 대국했다는 뜻이다.

같은 쌍이 여러 번 나올 수 있다. 모든 테스트 케이스의 $M$을 더한 값은 $10^6$ 이하다. 선수 번호는 1번부터 $2N$번까지이고, 기록과 어긋나지 않는 팀 배정은 항상 하나 이상 있다.

각 테스트 케이스마다 두 줄을 출력한다.

• 첫 줄에는 가능한 팀 배정의 수를 $10^8$으로 나눈 나머지를 출력한다. 출력하는 값은 0 이상 $10^8$ 미만이어야 한다. 배정이 존재해도 나머지가 0일 수 있다.
• 둘째 줄에는 1번 선수가 속한 팀의 선수 번호 $N$개를 오름차순으로, 공백 하나로 구분해 출력한다. 가능한 배정이 여러 개면 이 오름차순 수열이 사전순으로 가장 앞서는 배정을 출력한다.