CT43082

The Two Guilds of the Amber canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Nina inherited the loom house at the wren hedges of Thimblewick along with its curious bookkeeping system for canals. Time to make sense of it. 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 <= 1821; 0 <= m <= 3642; self-edges make the answer NO.

Example 1:

Input: 147 2090 95 145 41 69 14 84 61 105 11 76 82 117 33 75 79 109 55 142 40 117 102 121 41 81 17 136 60 114 121 126 9 21 44 45 49 120 41 53 49 73 73 105 77 109 5 26 4 138 52 145 132 147 15 67 48 91 5 95 65 71 57 89 68 69 91 94 61 112 23 63 26 70 12 73 84 111 55 60 110 114 28 123 24 95 9 105 10 51 4 78 84 87 9 19 82 128 33 146 68 88 32 101 57 107 52 83 74 107 50 74 22 98 65 128 95 114 19 87 18 132 109 140 44 119 35 99 52 99 37 73 130 140 83 89 47 141 130 133 96 102 67 73 69 101 55 98 21 120 50 81 67 103 8 114 31 47 44 93 118 135 88 107 21 75 3 62 52 123 15 22 29 67 114 121 5 9 14 74 43 91 29 135 10 44 21 133 30 77 14 27 22 139 32 53 44 137 41 116 70 104 72 112 101 106 6 144 13 140 2 139 127 142 17 116 120 143 61 110 18 134 88 126 54 71 13 65 24 102 5 125 72 91 33 39 114 135 25 92 95 140 85 96 1 …
Output: NO

Example 2:

Input: 950 587 615 824 99 426 319 539 437 517 294 550 429 668 296 751 75 866 68 206 389 891 627 921 275 747 637 754 634 846 98 685 569 950 557 838 615 916 853 866 132 529 370 510 28 50 132 445 12 896 735 901 487 827 346 418 544 924 716 869 406 772 48 378 322 795 120 231 270 490 199 702 108 631 233 565 119 657 501 943 715 810 232 537 91 556 16 393 463 946 54 395 244 687 253 839 574 866 582 601 14 545 175 723 6 740 436 597 116 366 290 745 240 289 332 468 537 739 536 906 462 502 345 516 449 695 524 854 196 899 116 827 880 908 219 751 878 935 247 788 102 705 492 904 133 299 617 950 273 652 669 724 440 746 225 389 779 938 263 731 107 364 309 563 98 899 486 565 616 800 420 430 134 342 74 93 615 647 257 679 73 225 410 649 243 885 86 812 73 784 722 879 434 905 498 579 570 778 20 199 3 564 773 779 203 493…
Output: NO

Example 3:

Input: 380 1297 8 109 86 142 75 82 169 176 42 119 276 293 207 289 146 350 148 295 287 331 12 158 87 104 130 137 252 378 14 295 105 287 114 132 64 98 106 149 209 275 27 172 72 356 147 281 231 314 284 314 259 273 105 181 158 259 45 365 193 364 2 315 121 125 240 312 148 365 63 257 314 334 58 100 29 283 73 128 55 230 10 150 141 290 50 316 4 122 48 112 140 176 114 273 28 186 15 280 118 344 120 218 55 181 146 187 195 318 128 190 43 78 33 258 94 280 113 330 342 379 185 366 198 324 115 247 12 339 74 285 265 314 46 130 309 338 16 214 132 309 74 114 33 307 108 279 170 371 32 153 69 155 131 325 20 157 202 363 81 233 55 370 8 118 19 263 93 144 114 267 277 298 170 223 227 263 229 298 330 360 137 358 23 66 297 319 45 168 2 200 173 206 41 372 214 361 290 326 80 141 237 306 98 230 332 371 159 375 151 175 57 163 …
Output: NO

Constraints:

1 <= n <= 1821; 0 <= m <= 3642; self-edges make the answer NO.

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