D. Пещерный человек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп нарисовал неориентированный граф из $$$n$$$ вершин и $$$m$$$ рёбер. Он хочет покрасить каждую вершину в красный или синий цвет так, чтобы у каждой вершины был хотя бы один сосед другого цвета. Ему нужно посчитать количество подходящих раскрасок.

Монокарп — пещерный человек: он знает только числа $$$1$$$, $$$2$$$ и «много» (любое число больше $$$2$$$). Про ноль он не знает, поэтому, если допустимых раскрасок нет, его мозг плавится.

Помогите Монокарпу посчитать допустимые раскраски на его языке. Две раскраски считаются различными, если хотя бы одна вершина имеет в них разные цвета.

Входные данные

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 3 \cdot 10^5$$$; $$$0 \le m \le \min\left(\frac{n(n-1)}{2}, 3 \cdot 10^5\right)$$$) — количество вершин и рёбер.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — номера вершин, соединённых $$$i$$$-м ребром. В графе нет петель и кратных рёбер.

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$; также сумма $$$m$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите в отдельной строке:

  • 1 или 2, если число допустимых раскрасок равно $$$1$$$ или $$$2$$$ соответственно;
  • Many, если допустимых раскрасок больше двух;
  • Brain Melt, если допустимых раскрасок нет.
Пример
Входные данные
4
3 1
1 2
3 2
1 2
1 3
3 3
1 2
2 3
1 3
4 3
1 2
2 3
3 4
Выходные данные
Brain Melt
2
Many
Many