problem.txt (2693B)
1 D. Caveman 2 time limit per test2 seconds 3 memory limit per test512 megabytes 4 Monocarp drew an undirected graph with n 5 vertices and m 6 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. 7 8 Monocarp is a caveman: he knows only the numbers 1 9 , 2 10 , and "many" (any number greater than 2 11 ). He does not know about zero, so if there are no valid colorings, his brain melts. 12 13 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. 14 15 Input 16 The first line contains an integer t 17 (1≤t≤104 18 ) — the number of test cases. 19 20 The first line of each test case contains two integers n 21 and m 22 (3≤n≤3⋅105 23 ; 0≤m≤min(n(n−1)2,3⋅105) 24 ) — the number of vertices and edges. 25 26 Each of the next m 27 lines contains two integers ui 28 and vi 29 (1≤ui,vi≤n 30 ) — the numbers of the vertices connected by the i 31 -th edge. The graph has no self-loops or multiple edges. 32 33 Additional constraints on the input: 34 35 the sum of n 36 over all test cases does not exceed 3⋅105 37 ; also the sum of m 38 over all test cases does not exceed 3⋅105 39 . 40 Output 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 44 or 2 45 respectively; 46 Many, if the number of valid colorings is greater than two; 47 Brain Melt, if there are no valid colorings. 48 49 --- 50 51 - n vertices, m edges, undirected graph 52 - two-coloring s.t. every vertex of a given color has at least one neighbor of the other color 53 - Two colorings are considered different if at least one vertex has a different color in them. 54 - this implies there are at least two colorings if a coloring is possible bc just swap the colors, no statement about isomorphism or the like 55 56 - cases: 57 - 2 58 - many (>2) 59 - brain melt (0) 60 61 --- 62 63 3 1 64 1 2 65 66 67 v := {1,2,3} 68 e := {{1,2}} 69 70 1 := blue 71 2 := red 72 3 := blue 73 74 no possible colorings like this because 3 is disconnected. generally, if there's a single disjoint vertex 0 is the answer 75 76 77 --- 78 79 3 2 80 1 2 81 1 3 82 83 84 {1,2,3} 85 {{1,2}, {2,3}} 86 87 1 := blue 88 2 := red 89 3 := blue 90 91 // heuristic: set the first element to be blue, second to red, unless first is red then second is blue (bipartite) 92 93 flip the colors is another option so return 2 94 95 --- 96 97 3 3 98 1 2 99 2 3 100 1 3 101 102 {1,2,3} 103 104 1,2 - 2,3 - 1,3 105 106 1 := blue 107 2 := red 108 3 := blue 109 110 since there's a cycle it seems we can do more colorings? 111 112 option 2: invert opt 1 113 114 option 3: 115 116 1 := blue 117 2 := blue 118 3 := red 119 120 --- 121 122 4 3 123 1 2 124 2 3 125 3 4 126 127 {1,2,3,4} 128 129 1 -> 2 130 2 -> 3 131 3 -> 4 132 133 1 := blue 134 2 := red 135 3 := blue 136 4 := red 137 138 invert 139 140 1 := blue 141 2 := red 142 3 := red 143 4 := blue 144 145 ---