Problem C
Map Colouring

Picture by: Inductiveload

A map maker wants to colour different countries or provinces on his maps using different colours. That is, he wants to colour countries that share a common border with a different colour. He has heard that any map can be coloured with four colours, but even after a lot of puzzling he is unable to colour some of his maps using four colours. Interested in the problem, and hoping that he can publish four-coloured maps, the map maker visits you for help.

After inspecting his maps you explain to the map maker that not every map can be coloured with four colours. You tell him that when countries are made up of different non-connected parts (such as Alaska and the rest of the United States), it can be the case that one needs more colours. Also, if the maps contains a quadripoint (a point where four countries touch), it can also be the case that one needs more colours. The same is true when more than four countries meet in one point.

Disappointed, the map maker asks you whether you cannot help him in quickly deciding how many colours he needs. While you try to explain that this is a quite difficult question, he shows you his maps. After a lot of persuasion by him, and the realisation that all his maps are actually very small, you agree to make a computer program for him. You agree to write a program for his small maps (at most 16 countries) that determines whether his map can be coloured with 1, 2, 3, 4 or more colours. This program should still work if there are non-connected countries, quadripoints, etc.

Input

The input starts with a line containing an integer $T$ ($1 \leq T \leq 33$), the number of test cases. Then for each test case:

• One line with two space-separated integers $C$ and $B$, indicating the number of countries $C$ ($1 \leq C \leq 16$) and the number of borders $B$ ($0 \leq B \leq 120$).

• $B$ lines with two space-separated integers $i$ and $j$ ($0 \leq i, j \leq C-1$ and $i \neq j$), indicating that there is a border between country $i$ and country $j$.

Output

For each test case, output a single line containing either an integer $K$, or the string ’many’. Your program should output the integer $K$, where $K$ is the minimum number of colours needed to colour the map if this number is 1, 2, 3 or 4. Your program should output ’many’ if this number is larger.

3
4 0
4 4
0 1
1 2
2 3
3 0
5 10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

1
2
many