2276D.md (1822B)
1 Source: https://codeforces.com/problemset/problem/2276/D 2 3 D. Caveman 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Monocarp drew an undirected graph with $n$ vertices and $m$ 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. 22 23 Monocarp is a caveman: he knows only the numbers $1$, $2$, and "many" (any number greater than $2$). He does not know about zero, so if there are no valid colorings, his brain melts. 24 25 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. 26 27 Input 28 29 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The first line of each test case contains two integers $n$ and $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)$) — the number of vertices and edges. 32 33 Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) — the numbers of the vertices connected by the $i$-th edge. The graph has no self-loops or multiple edges. 34 35 Additional constraints on the input: 36 37 * the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$; also the sum of $m$ over all test cases does not exceed $3 \cdot 10^5$. 38 39 Output 40 41 For each test case, print on a separate line: 42 43 * 1 or 2, if the number of valid colorings is equal to $1$ or $2$ respectively; 44 * Many, if the number of valid colorings is greater than two; 45 * Brain Melt, if there are no valid colorings. 46 47 Example 48 49 Input 50 51 ``` 52 4 53 54 3 1 55 56 1 2 57 58 3 2 59 60 1 2 61 62 1 3 63 64 3 3 65 66 1 2 67 68 2 3 69 70 1 3 71 72 4 3 73 74 1 2 75 76 2 3 77 78 3 4 79 ``` 80 81 Output 82 83 ``` 84 Brain Melt 85 86 2 87 88 Many 89 90 Many 91 ```