Map Colouring

A map maker colours the countries on his maps so that two countries sharing a border always get different colours. He has heard that four colours are enough for any map, but some of his maps defeat him no matter how long he works on them. He wants to publish four-coloured maps, so he asks you for help.

After looking at the maps you explain that not every map can be coloured with four colours. A country made of separate parts, such as Alaska and the rest of the United States, can force extra colours. So can a point where four countries touch, and a point where more than four countries touch.

His maps are small, at most 16 countries each, so you agree to write the program. A map is given as a number of countries and a list of borders. Two countries joined by a border must get different colours. Find the smallest number of colours that colours the whole map, and decide whether that number is 1, 2, 3, 4, or larger. The program has to work when a country has separate parts and when several countries meet at one point.

The first line contains an integer $T$, the number of test cases. Each test case is given as follows.

• One line with two space-separated integers $C$ and $B$, the number of countries and the number of borders. ($1 \le C \le 16$, $0 \le B \le 120$)
• $B$ lines, each with two space-separated integers $i$ and $j$ ($0 \le i, j \le C - 1$, $i \ne j$), meaning that country $i$ and country $j$ share a border.

For each test case, print one line. If the smallest number of colours needed is 1, 2, 3 or 4, print that number. If it is larger, print many.