#391. D. Caveman☆Favorite(穴居人的双色染色)
D. Caveman☆Favorite(穴居人的双色染色)
题目描述
Monocarp 画了一张包含 个顶点、 条边的无向简单图。
他想将每个顶点染成红色或蓝色,并要求:每个顶点都至少有一个与它颜色不同的相邻顶点。
Monocarp 是一名穴居人,只认识数字 1、2 和 Many(表示大于 的任意整数)。他不认识零,所以如果不存在符合要求的染色方案,他的大脑就会融化(Brain Melt)。
请用 Monocarp 能理解的方式输出合法的染色方案数量。
如果两种染色方案中至少有一个顶点的颜色不同,则认为这两种方案不同。
输入格式
第一行包含一个整数 (),表示测试用例的数量。
对于每组测试用例:
- 第一行包含两个整数 (,$0\le m\le\min\left(\frac{n(n-1)}2,3\times10^5\right)$),分别表示顶点数与边数。
- 接下来 行,每行包含两个整数 (),表示顶点 与顶点 之间有一条无向边。
保证图中没有自环,也没有重边。
保证所有测试用例的顶点数总和不超过 ,边数总和也不超过 。
输出格式
对每组测试用例输出一行:
- 如果合法染色方案数等于 或 ,分别输出
1或2; - 如果合法染色方案数大于 ,输出
Many; - 如果不存在合法染色方案,输出
Brain Melt。
注意: 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
样例说明
- 第 1 组: 顶点 没有邻居,因此不存在合法染色方案。
- 第 2 组: 图是一棵星形树,只有交换红蓝两色得到的两种合法方案,因此输出
2。 - 第 3 组: 图为三角形,合法染色方案有超过两种,因此输出
Many。 - 第 4 组: 图是一条由四个顶点组成的路径,也存在超过两种合法染色方案。
数据范围与限制
- 时间限制:2 秒。
- 内存限制:512 MiB。
- 。
- 。
- $0\le m\le\min\left(\frac{n(n-1)}2,3\times10^5\right)$。
- 每个输入文件中,所有测试用例的 之和、 之和均不超过 。