CF2276D.Caveman

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:512MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Monocarp drew an undirected graph with nn vertices and mm edges. He wants to color each vertex red or blue so that every vertex has at least one neighbor of the opposite color. He needs to calculate the number of colorings that suit him.

Monocarp is a caveman: he knows only the numbers 11, 22, and "many" (any number greater than 22). He does not know about zero, so if there are no valid colorings, his brain melts.

Help Monocarp count the valid colorings in his language. Two colorings are considered different if at least one vertex has a different color in them.

Monocarp 画了一个包含 nn 个顶点和 mm 条边的无向图。他希望将每个顶点染成红色或蓝色,使得每个顶点至少有一个与其颜色相反的邻居。他需要计算满足条件的染色方案数。

Monocarp 是一个原始人:他只知道数字 11、22 和“很多”(即任意大于 22 的数)。他不知道零的概念,因此如果不存在任何合法的染色方案,他的大脑就会熔化。

请帮助 Monocarp 用他的语言计算合法染色方案数。若两种染色方案中至少有一个顶点的颜色不同,则认为它们是不同的染色方案。

输入格式

The first line contains an integer tt (1≤t≤1041 \le t \le 10^4) — the number of test cases.

The first line of each test case contains two integers nn and mm (3≤n≤3⋅1053 \le n \le 3 \cdot 10^5; 0≤m≤min⁡(n(n−1)2,3⋅105)0 \le m \le \min\left(\frac{n(n-1)}{2}, 3 \cdot 10^5\right)) — the number of vertices and edges.

Each of the next mm lines contains two integers uiu_i and viv_i (1≤ui,vi≤n1 \le u_i, v_i \le n) — the numbers of the vertices connected by the ii-th edge. The graph has no self-loops or multiple edges.

Additional constraints on the input:

  • the sum of nn over all test cases does not exceed 3⋅1053 \cdot 10^5; also the sum of mm over all test cases does not exceed 3⋅1053 \cdot 10^5.

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

每个测试用例的第一行包含两个整数 nn 和 mm(3≤n≤3⋅1053 \le n \le 3 \cdot 10^5;0≤m≤min⁡(n(n−1)2,3⋅105)0 \le m \le \min\left(\frac{n(n-1)}{2}, 3 \cdot 10^5\right))—— 图的顶点数和边数。

接下来的 mm 行中,每行包含两个整数 uiu_i 和 viv_i(1≤ui,vi≤n1 \le u_i, v_i \le n)—— 表示第 ii 条边所连接的两个顶点的编号。图中不存在自环或重边。

输入的额外约束条件:

  • 所有测试用例的 nn 之和不超过 3⋅1053 \cdot 10^5;所有测试用例的 mm 之和也不超过 3⋅1053 \cdot 10^5。

输出格式

For each test case, print on a separate line:

  • 1 or 2, if the number of valid colorings is equal to 11 or 22 respectively;
  • Many, if the number of valid colorings is greater than two;
  • Brain Melt, if there are no valid colorings.

对于每个测试用例,在单独一行中输出:

  • 若有效着色方案的数量等于 11 或 22,则分别输出 1 或 2;
  • 若有效着色方案的数量大于二,则输出 Many;
  • 若不存在有效着色方案,则输出 Brain Melt。

输入输出样例

  • 输入#1

    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

    输出#1

    Brain Melt
    2
    Many
    Many

说明/提示

null

输入解题思路,AI测评打分。不知道怎么写?

首页