CF2276D Caveman

Monocarp 画了一个无向图，其中有 $n$ 个顶点和 $m$ 条边。他希望将每个顶点染成红色或蓝色，并满足每个顶点至少有一个相邻的顶点颜色与其不同。他需要计算有多少种满足条件的染色方案。 Monocarp 是个原始人：他只认识数字 $1$、$2$ 和“many”（表示大于 $2$ 的任何数字）。他不知道零的概念，因此如果没有满足条件的染色方案，他会“脑子宕机”。 请帮 Monocarp 用他的方式统计合法的染色方案数。如果存在多个染色方案，只要任意一个点的染色不同，这些方案就被认为是不同的。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的个数。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \leq n \leq 3 \times 10^5$；$0 \leq m \leq \min\left(\frac{n(n-1)}{2}, 3 \times 10^5\right)$），表示顶点和边的数量。 接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示第 $i$ 条边所连接的两个顶点的编号。图中没有自环和重边。 输入的额外限制： - 所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$，$m$ 的总和也不超过 $3 \times 10^5$。

对于每个测试用例，单独输出一行： - 如果合法染色方案数为 $1$，输出 1。 - 如果合法染色方案数为 $2$，输出 2。 - 如果方案数大于 $2$，输出 Many。 - 如果没有合法方案，输出 Brain Melt。

由 ChatGPT 5 翻译