#391. D. Caveman☆Favorite(穴居人的双色染色)

    ID: 391 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>其他构造图论无向图分类讨论CF

D. Caveman☆Favorite(穴居人的双色染色)

题目描述

Monocarp 画了一张包含 nn 个顶点、mm 条边的无向简单图。

他想将每个顶点染成红色或蓝色,并要求:每个顶点都至少有一个与它颜色不同的相邻顶点。

Monocarp 是一名穴居人,只认识数字 1、2 和 Many(表示大于 22 的任意整数)。他不认识零,所以如果不存在符合要求的染色方案,他的大脑就会融化(Brain Melt)。

请用 Monocarp 能理解的方式输出合法的染色方案数量。

如果两种染色方案中至少有一个顶点的颜色不同,则认为这两种方案不同。

输入格式

第一行包含一个整数 tt(1≤t≤1041\le t\le 10^4),表示测试用例的数量。

对于每组测试用例:

  • 第一行包含两个整数 n,mn,m(3≤n≤3×1053\le n\le 3\times10^5,$0\le m\le\min\left(\frac{n(n-1)}2,3\times10^5\right)$),分别表示顶点数与边数。
  • 接下来 mm 行,每行包含两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n),表示顶点 uiu_i 与顶点 viv_i 之间有一条无向边。

保证图中没有自环,也没有重边。

保证所有测试用例的顶点数总和不超过 3×1053\times10^5,边数总和也不超过 3×1053\times10^5。

输出格式

对每组测试用例输出一行:

  • 如果合法染色方案数等于 11 或 22,分别输出 1 或 2;
  • 如果合法染色方案数大于 22,输出 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 组: 顶点 33 没有邻居,因此不存在合法染色方案。
  • 第 2 组: 图是一棵星形树,只有交换红蓝两色得到的两种合法方案,因此输出 2。
  • 第 3 组: 图为三角形,合法染色方案有超过两种,因此输出 Many。
  • 第 4 组: 图是一条由四个顶点组成的路径,也存在超过两种合法染色方案。

数据范围与限制

  • 时间限制:2 秒。
  • 内存限制:512 MiB。
  • 1≤t≤1041\le t\le 10^4。
  • 3≤n≤3×1053\le n\le 3\times10^5。
  • $0\le m\le\min\left(\frac{n(n-1)}2,3\times10^5\right)$。
  • 每个输入文件中,所有测试用例的 nn 之和、mm 之和均不超过 3×1053\times10^5。