from collections import defaultdict
from sys import stdin

def dfs(i, colours, prev, min_found):
    colours[i - 1] = prev
    if i == C:
        tmp = max(colours)
        if tmp < min_found:
            min_found = tmp
        return min_found

    current = set()
    for j in borders[i]:
        if colours[j] != 0:
            current.add(colours[j])

    for j in range(1, 5):
        if j not in current:
            min_found = min(min_found, dfs(i + 1, colours, j, min_found))
    return min_found

T = int(input())
for _ in range(T):
    C, B = [int(x) for x in stdin.readline().split()]
    borders = defaultdict(list)
    for _ in range(B):
        i, j = [int(x) for x in stdin.readline().split()]
        borders[i].append(j)
        borders[j].append(i)

    min_found = 5
    colours = [0]*C
    if B == 0:
        min_found = 1
    else:
        min_found = dfs(1, colours, 1, min_found)

    if min_found > 4:
        print('many')
    else:
        print(min_found)