CT39045

Rosa's roads Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Rosa the scribe watches over the floating docks of Skyharbor's stores of roads. A careful computation stands between order and chaos. 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 <= 2955; 0 <= m <= 5910; self-edges make the answer NO.

Example 1:

Input: 2162 3781 1 2 2 3 1 3 837 1033 1261 1600 180 355 1609 2122 963 991 1075 1940 1020 1966 32 137 438 780 267 2036 1078 1191 1005 1290 611 1538 1848 2141 103 455 256 1241 272 449 1007 1633 25 210 1205 2096 341 1242 635 2007 863 1122 568 974 484 2035 409 1209 22 1371 1182 1694 1216 1728 285 1296 1282 1992 557 661 1711 1932 143 1740 138 695 1325 1420 731 970 231 467 749 1794 1025 1939 181 506 618 1518 586 1270 89 973 1968 1981 229 433 79 861 132 1010 1324 2146 1024 1485 184 502 1527 1934 784 1901 804 1452 462 486 349 2016 246 1381 475 1923 684 741 804 1005 1429 1537 1057 2053 1130 1672 813 954 1026 1468 609 1614 447 851 56 1136 311 1874 111 839 6 635 1067 1299 85 679 1688 2160 1265 1602 211 1783 433 911 1338 1766 467 694 864 908 113 1167 805 1009 227 771 1477 1577 929 1271 183 1856 399 716 580 1…
Output: NO

Example 2:

Input: 1063 2242 250 669 434 483 86 463 328 746 89 145 826 903 900 983 400 666 117 841 223 384 52 813 550 717 312 896 52 847 481 735 161 630 552 866 413 644 346 922 425 688 976 978 446 925 637 795 99 366 115 790 276 781 188 582 446 840 676 1030 745 1033 132 952 546 1041 569 796 43 428 684 766 1015 1044 99 143 358 361 549 600 113 858 135 735 91 780 112 360 315 986 491 550 240 290 743 792 324 848 145 228 676 843 271 519 732 775 180 861 87 946 192 435 319 432 148 841 114 929 252 510 67 566 156 478 83 801 217 1036 473 671 455 807 445 610 576 884 465 1056 315 332 101 945 42 838 294 698 208 886 798 1006 493 530 292 329 555 961 354 627 82 449 158 774 216 281 623 824 68 165 575 896 534 785 175 867 173 405 581 699 214 870 301 1005 6 580 270 571 373 493 108 367 618 833 137 393 45 459 142 419 148 292 126 67…
Output: NO

Example 3:

Input: 1034 539 659 1006 170 852 691 732 386 514 546 721 332 804 78 641 602 876 48 99 190 356 12 817 86 875 516 551 265 591 237 471 179 214 557 911 327 648 395 975 248 747 467 821 193 752 136 763 49 146 469 896 436 660 311 573 80 272 115 135 496 665 292 756 212 809 116 187 178 219 508 957 426 431 123 416 27 473 80 133 212 897 636 984 172 270 680 718 664 869 343 649 232 411 405 946 56 1004 899 935 661 824 492 857 109 881 508 660 615 842 35 755 128 277 468 1032 412 830 484 488 696 803 304 466 613 652 136 586 482 796 637 907 120 701 27 908 465 753 634 938 74 467 288 310 661 754 49 53 106 329 653 966 44 842 672 715 545 584 1 598 190 664 741 863 271 568 38 879 966 1019 508 629 383 928 152 324 984 996 95 399 386 533 70 742 582 736 110 271 215 236 343 598 798 964 404 890 496 558 35 237 636 932 200 630 1…
Output: NO

Constraints:

1 <= n <= 2955; 0 <= m <= 5910; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Rosa's roads Reckoning - MEDIUM Coding Problem | CodeTikki