지도 색칠하기

지도 제작자는 자신의 지도에 있는 나라를 서로 다른 색으로 칠하려고 한다. 국경을 맞댄 두 나라는 반드시 색이 달라야 한다. 어떤 지도든 네 가지 색이면 칠할 수 있다는 말을 들었지만, 아무리 궁리해도 네 색으로 칠하지 못하는 지도가 있었다. 네 색으로 칠한 지도를 펴내고 싶었던 그는 도움을 청하러 당신을 찾아왔다.

지도를 살펴본 당신은 모든 지도를 네 색으로 칠할 수 있는 것은 아니라고 설명한다. 알래스카와 미국 본토처럼 한 나라가 서로 떨어진 여러 조각으로 이루어져 있으면 색이 더 필요할 수 있다. 네 나라가 한 점에서 만나도 그럴 수 있고, 다섯 나라 이상이 한 점에서 만나도 마찬가지다.

그의 지도는 모두 작아서 나라가 많아야 16개다. 그래서 당신은 프로그램을 만들어 주기로 한다. 지도는 나라의 수와 국경 목록으로 주어진다. 국경으로 이어진 두 나라는 서로 다른 색을 써야 한다. 지도 전체를 칠하는 데 필요한 색의 최소 개수를 구하고, 그 수가 1, 2, 3, 4 중 하나인지 아니면 그보다 큰지 판정하라. 나라가 떨어진 조각으로 나뉘어 있거나 여러 나라가 한 점에서 만나는 경우에도 프로그램은 올바르게 동작해야 한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같은 형식이다.

• 첫 줄에 나라의 수 $C$와 국경의 수 $B$가 공백으로 구분되어 주어진다. ($1 \le C \le 16$, $0 \le B \le 120$)
• 다음 $B$개의 줄에는 두 정수 $i$와 $j$가 공백으로 구분되어 주어진다. ($0 \le i, j \le C - 1$, $i \ne j$) 나라 $i$와 나라 $j$가 국경을 맞대고 있다는 뜻이다.

각 테스트 케이스마다 한 줄을 출력한다. 필요한 색의 최소 개수가 1, 2, 3, 4 중 하나이면 그 수를 출력하고, 그보다 크면 many를 출력한다.