CT58588

The roads Two Guilds Puzzle

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Wynne inherited the studio at the kelp forests of Tangledeep along with its curious bookkeeping system for roads. 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 <= 975; 0 <= m <= 1950; self-edges make the answer NO.

Example 1:

Input: 913 198 512 595 449 889 172 562 240 269 371 396 725 870 220 431 48 627 479 796 97 184 192 797 702 819 571 601 191 768 86 499 288 873 12 45 5 703 262 668 193 885 254 473 26 133 365 437 319 453 216 828 33 457 171 474 307 482 59 689 411 629 91 597 717 824 445 525 512 817 382 780 41 257 683 709 432 634 122 871 476 561 672 887 252 568 19 781 422 855 82 884 144 708 226 565 131 232 20 143 384 648 360 523 547 778 82 707 338 536 292 808 302 735 67 692 659 777 777 845 6 467 306 315 125 663 136 476 92 543 205 396 220 597 11 744 264 587 413 693 714 718 265 716 524 553 203 218 24 251 375 467 553 683 314 669 258 624 312 880 551 612 476 631 119 599 18 696 369 386 115 747 410 506 128 656 76 881 613 641 20 876 219 908 95 402 736 751 307 532 76 391 51 317 268 852 158 290 455 800 155 345 61 352 90 333 465 56…
Output: YES

Example 2:

Input: 2 1 1 2
Output: YES

Example 3:

Input: 961 356 1 2 2 3 1 3 312 422 302 667 181 855 502 569 282 695 739 954 620 910 630 837 251 439 279 398 375 760 556 907 185 912 35 786 133 547 315 363 838 961 394 819 31 654 30 615 645 951 241 922 351 564 223 545 179 646 124 207 827 849 682 808 443 787 219 420 86 252 395 861 442 731 69 653 43 861 453 879 301 795 198 499 334 907 342 656 583 926 595 657 188 348 193 897 371 528 450 688 119 734 732 784 872 893 84 598 45 631 502 928 546 744 254 849 192 843 420 817 637 710 216 830 48 641 411 492 611 641 391 495 227 823 15 375 89 678 188 265 134 887 782 862 367 827 247 638 309 531 749 852 59 608 289 613 645 948 905 930 174 881 83 883 420 512 162 829 397 412 804 819 455 810 100 242 514 656 579 822 154 932 172 553 323 598 316 548 303 901 243 961 192 214 108 518 256 301 107 368 495 924 344 437 853 938 1…
Output: NO

Constraints:

1 <= n <= 975; 0 <= m <= 1950; self-edges make the answer NO.

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