CT43176

Ulmar and the Shimmering tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the rook towers of Chessfield, Ulmar studies rows of tunnels entries. One clean number will settle the guild's oldest argument. 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 <= 1203; 0 <= m <= 2406; self-edges make the answer NO.

Example 1:

Input: 968 517 24 366 185 824 409 740 47 749 427 480 395 664 634 805 285 829 234 318 836 898 170 959 181 900 175 919 482 938 262 582 544 938 54 91 99 597 614 923 572 721 125 881 666 899 672 804 578 626 744 780 21 729 6 27 708 748 576 666 36 951 502 723 717 757 661 928 2 616 244 614 496 882 267 861 402 416 12 802 250 866 529 547 556 581 216 323 164 858 138 457 288 478 344 360 386 612 127 507 417 760 734 936 226 708 417 674 37 271 843 865 4 559 163 693 177 531 404 789 452 891 496 692 508 718 230 386 68 493 313 663 166 479 324 381 356 852 102 483 187 581 210 963 370 391 33 388 558 912 477 819 272 774 93 685 136 817 590 920 376 393 210 517 372 589 128 428 502 918 490 885 279 778 314 873 407 576 336 476 707 955 296 950 631 644 192 636 314 552 356 944 43 486 71 578 381 802 132 231 741 897 378 554 188 7…
Output: NO

Example 2:

Input: 959 9 1 2 2 3 1 3 307 665 637 745 475 517 300 827 389 508 348 764
Output: NO

Example 3:

Input: 175 2401 74 160 16 158 31 81 67 175 21 153 45 117 132 137 140 168 22 136 33 118 38 60 143 165 137 168 25 29 26 36 83 107 16 48 3 171 15 59 8 163 131 171 32 62 13 73 57 63 108 152 29 164 155 169 121 127 36 120 142 166 44 50 58 175 96 167 60 137 13 43 40 106 130 150 77 172 96 114 29 134 53 157 30 103 133 145 27 155 54 160 143 167 37 129 8 17 109 145 28 141 59 101 1 98 12 44 1 127 14 57 16 97 34 86 104 129 77 136 39 133 84 149 91 119 35 98 58 70 21 45 32 43 107 154 96 109 94 127 8 101 45 149 102 137 13 133 2 96 62 102 128 156 96 120 6 104 11 110 65 74 18 115 25 57 86 165 58 136 122 153 7 45 52 140 102 103 47 88 94 156 80 104 46 123 44 73 126 175 122 135 57 109 86 163 14 163 14 36 96 147 22 46 111 124 128 159 34 93 139 162 4 109 6 96 80 131 34 139 5 90 66 169 50 164 86 168 10 113 73 148 63 90 …
Output: NO

Constraints:

1 <= n <= 1203; 0 <= m <= 2406; self-edges make the answer NO.

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