题目描述

莫诺卡普画了一张有 $n$ 个顶点、$m$ 条边的无向图。他想把每个顶点染成红色或者蓝色，使得每个顶点都至少有一个异色的相邻点。他需要求出满足条件的染色方案数量。

莫诺卡普是一个穴居人：他只认识数字 $1$、$2$，以及“Many”（任意大于 $2$ 的数）。他不知道数字 $0$，所以如果不存在合法染色方案，他的大脑就会融化。

请你用他能理解的语言帮他统计合法染色方案数。两种染色方案不同，当且仅当至少有一个顶点的颜色不一样。

输入格式

第一行一个整数 $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$，输出 1；等于 $2$，输出 2；
• 如果合法方案数大于 $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

原题链接

原题链接