Chess Tournament

A big chess tournament is being held in your town, so you go and watch. Two teams A and B, each with $n$ players, face each other, and every player of team A plays one game against every player of team B. The team with more wins takes the title. In a drawn game each player gets $1/2$ point.

You do not know which players are on which team, but you wrote down every game played during the tournament. The catch is that some players also played outside the schedule, for practice or for fun. Some of those games were against a teammate, some against an opponent they had already faced. Can you still tell who belongs to which team?

Count the team assignments that agree with your list, that is, the assignments in which every pair of players from opposite teams appears in the list at least once. The two teams have no names, so swapping A and B gives the same assignment.

The first line has the number of test cases $T$ ($1 \le T \le 100$). Each test case is given as follows.

• One line with two integers $N$ and $M$, the number of players per team and the number of recorded games ($1 \le N \le 250$, $N^2 \le M \le 10^6$).
• Then $M$ lines, each with two different integers $A$ and $B$ ($1 \le A < B \le 2N$), meaning that player $A$ and player $B$ played a game.

The same pair may appear more than once. The sum of $M$ over all test cases is at most $10^6$. Players are numbered 1 through $2N$, and at least one assignment that agrees with the list always exists.

For each test case print two lines.

• The first line has the number of assignments modulo $10^8$. The printed value must be at least 0 and less than $10^8$. The remainder can be 0 even though an assignment exists.
• The second line has the $N$ players of the team that contains player 1, in increasing order, separated by single spaces. When several assignments are possible, print the one whose increasing sequence is lexicographically smallest.