CT47046

Axel and the Two Guilds

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Axel runs the signal tower at the pine barrens of Needlepoint. Today the books show a list of bridges, and the numbers must be worked out before sundown. Task: Print YES if the undirected graph's nodes can be split into two groups with no edge inside a group, otherwise NO. Input format: First line: n and m. Next m lines: u v. Output format: Print YES or NO. Constraints: 1 <= n <= 2772; 0 <= m <= 5544; self-edges make the answer NO.

Example 1:

Input: 166 831 1 2 2 3 1 3 92 130 40 96 26 145 44 155 91 147 20 163 13 72 47 165 81 151 19 103 47 69 45 107 12 13 1 107 117 136 111 162 101 149 87 143 105 158 79 143 2 119 97 105 12 110 76 85 123 163 104 132 62 72 19 21 44 159 50 94 71 98 106 111 11 114 108 116 160 164 56 150 36 160 2 141 70 155 30 102 100 109 124 128 69 72 8 126 56 134 61 66 41 101 62 139 80 135 8 152 82 98 44 87 130 151 67 80 1 163 39 151 28 70 6 11 17 34 6 130 72 163 117 140 96 136 61 69 95 137 110 138 6 119 12 40 87 159 26 96 134 163 65 72 74 83 13 134 58 75 68 96 118 131 12 17 55 153 14 94 61 161 4 46 84 149 18 85 74 135 105 124 23 25 44 135 90 152 6 25 49 129 35 77 40 45 115 142 97 160 70 128 89 103 18 142 24 165 45 130 105 126 91 108 131 150 134 158 27 45 74 151 1 15 121 156 72 73 90 118 4 85 7 151 123 166 6 21 37 132 92 1…
Output: NO

Example 2:

Input: 2160 2630 1 2 2 3 1 3 304 1907 480 1002 156 1931 196 1375 514 1062 1172 1620 343 1417 166 1182 190 1945 539 976 923 1070 284 1761 76 657 1583 1966 1150 1175 1548 1989 267 1864 319 1495 1519 1582 142 715 1498 1594 21 562 25 1415 288 441 159 2160 165 1524 963 1554 1570 1733 20 1720 1706 1931 165 747 664 847 1850 1891 656 1282 271 1929 1528 1840 552 1858 140 934 1168 2002 800 1635 892 1254 984 1071 138 1487 1029 1875 1745 2080 788 1850 613 1437 686 1518 1521 2109 1658 2113 932 1451 559 830 23 452 133 164 398 495 953 1356 666 2121 638 1972 1339 1613 668 947 432 1668 334 1634 233 1300 61 557 1157 2091 1030 1636 17 525 229 1506 361 1944 115 1373 803 1126 369 1199 1191 2070 1255 1705 1779 1914 440 968 458 1978 750 2046 1635 2052 296 521 587 1606 1146 1980 796 845 213 524 1886 1895 1354 1479 1066 …
Output: NO

Example 3:

Input: 387 2751 165 254 202 323 121 156 46 354 222 344 72 298 16 375 267 339 42 175 291 329 261 333 30 212 106 289 185 240 84 180 176 272 201 222 2 348 216 370 70 255 278 362 126 344 72 85 60 285 8 261 37 361 104 281 139 355 57 161 197 315 8 383 282 292 90 201 131 256 69 106 25 79 54 90 68 196 159 220 72 158 43 158 5 186 56 152 10 330 245 325 250 338 79 259 36 205 306 322 339 355 128 189 43 334 24 109 66 275 335 358 91 159 30 222 36 343 67 264 184 317 110 190 274 289 89 119 89 325 99 306 250 302 59 379 218 318 84 311 103 157 157 292 105 131 359 370 173 240 69 206 186 275 222 377 155 227 150 153 136 326 347 378 119 375 47 364 73 344 128 217 79 197 180 242 227 384 83 127 4 52 30 280 316 321 77 343 23 267 314 360 57 95 297 303 72 247 88 137 248 387 106 339 13 23 190 347 93 286 27 321 139 219 40 345 …
Output: NO

Constraints:

1 <= n <= 2772; 0 <= m <= 5544; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.