CT61421

Nyssa's Ledger of canals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the temple city of Sunspire opens only for a perfect tally of canals. Nyssa means to find out. 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 <= 1200; 0 <= m <= 2400; self-edges make the answer NO.

Example 1:

Input: 254 1588 1 2 2 3 1 3 145 152 55 201 183 251 58 222 76 246 176 229 63 153 105 157 40 200 32 62 168 199 66 225 61 130 15 51 117 230 137 189 30 135 191 251 101 191 45 205 69 192 19 234 58 60 56 233 27 193 136 183 229 235 36 93 71 224 172 216 20 104 115 231 25 222 172 249 115 166 41 167 159 236 43 173 83 166 239 243 36 74 83 101 9 76 109 234 93 140 25 47 106 146 78 167 167 185 9 157 76 130 140 242 169 181 168 233 35 181 6 143 66 119 195 201 2 93 73 184 35 60 145 163 59 106 16 53 48 177 3 180 30 137 15 158 93 121 23 178 134 250 191 245 23 194 82 231 94 113 73 132 194 223 94 195 101 175 17 55 10 68 235 241 117 139 98 110 133 246 1 41 77 245 29 93 180 203 228 234 163 249 212 228 59 136 77 158 112 115 98 184 97 195 18 163 38 41 88 181 89 231 152 236 170 245 90 224 24 47 66 239 144 242 58 234 48 17…
Output: NO

Example 2:

Input: 797 60 662 705 265 522 174 598 231 628 58 740 358 407 303 643 139 453 538 557 24 385 231 411 171 341 193 318 44 129 17 670 18 510 581 757 440 471 3 675 255 586 143 794 207 648 446 558 670 781 132 516 129 308 105 660 537 629 617 734 515 641 621 628 492 781 518 562 630 672 620 790 376 603 194 404 79 731 203 407 413 680 574 757 85 500 115 751 510 661 658 679 514 580 449 758 508 684 471 605 28 489 335 498 442 550 8 348 136 162 585 650 437 548 405 711 664 675 44 334 699 717
Output: YES

Example 3:

Input: 881 675 406 427 113 613 2 872 180 467 120 781 526 593 555 624 819 841 116 846 331 694 145 184 230 743 660 825 183 305 244 292 8 521 658 718 427 448 583 660 578 708 311 530 278 467 481 853 479 605 470 501 33 342 413 736 152 785 500 610 217 768 323 338 25 59 35 183 173 481 371 812 465 513 554 867 102 210 458 529 342 856 81 211 7 115 673 806 113 463 780 795 617 722 57 639 317 659 275 360 149 661 471 736 655 711 440 838 6 69 538 838 742 803 34 286 145 418 18 629 180 575 50 710 745 749 284 392 626 832 490 833 473 627 10 379 133 879 126 773 36 429 520 609 213 283 272 323 48 652 118 688 109 498 653 762 343 400 46 221 99 761 172 650 532 619 274 836 309 858 28 385 174 294 30 745 439 632 188 525 79 420 58 525 29 842 16 688 6 360 3 469 26 515 167 623 76 694 490 873 218 800 647 781 72 190 334 791 290 …
Output: NO

Constraints:

1 <= n <= 1200; 0 <= m <= 2400; self-edges make the answer NO.

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