CT47139

Wynne's Caramel Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the northern keep of Frostgate, Wynne records each roads in a worn leather ledger. The guild wants answers, not guesses. 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 <= 2701; 0 <= m <= 5402; self-edges make the answer NO.

Example 1:

Input: 2465 1967 1 2 2 3 1 3 1082 1434 471 1743 504 2140 838 1864 177 350 425 2169 411 1871 689 1390 1179 1864 934 2175 2234 2394 22 546 1126 1766 1094 1431 88 2004 1131 1743 533 586 1578 2139 108 1130 73 2100 661 2124 824 1556 918 2429 1095 1979 467 1501 153 251 1150 2230 1476 1987 193 1674 1276 2149 259 986 297 2197 402 1320 406 469 991 1960 903 2133 9 1592 858 1230 828 1991 309 523 629 2012 470 1390 811 1422 51 2174 697 1476 199 2396 272 1465 1167 2144 671 2384 711 1479 1777 2180 732 1721 1278 2409 462 864 1685 2049 1824 1965 1785 1970 87 733 785 1627 501 1344 1419 2411 1199 2459 799 980 1178 1850 9 1931 41 1138 115 2386 837 1242 1108 1134 1363 2308 856 2276 487 1463 281 681 734 1578 850 1759 701 980 182 686 704 1249 1936 2384 4 1789 968 2021 357 1162 1956 2040 1569 1703 1391 1656 2101 2259 79…
Output: NO

Example 2:

Input: 1148 3462 325 570 810 1107 248 499 153 320 446 749 347 467 322 674 181 1009 201 279 3 525 438 770 329 1104 15 386 993 1079 293 813 617 1128 396 972 512 1009 847 881 1 260 394 524 197 1108 199 349 417 805 350 798 1053 1109 44 951 611 997 486 905 36 836 556 761 726 1095 239 1062 637 827 139 486 282 866 181 350 272 551 210 1044 375 668 248 683 103 883 472 710 251 1096 294 468 337 545 398 419 517 735 471 758 820 951 328 458 578 675 184 435 66 442 528 807 765 849 753 754 61 829 71 463 128 635 308 359 233 1104 431 891 42 1019 450 581 352 1090 867 1057 656 962 334 830 327 356 335 1121 522 569 1098 1128 135 1015 187 695 157 674 67 512 339 405 319 1030 887 977 255 304 305 379 583 1056 702 963 898 1013 218 962 818 851 534 952 80 851 336 915 950 1126 664 948 949 1105 52 204 382 404 420 1022 197 1140 …
Output: NO

Example 3:

Input: 7 12 1 6 2 4 1 2 1 3 2 7 3 5 3 4 5 7 1 4 3 7 1 7 2 6
Output: NO

Constraints:

1 <= n <= 2701; 0 <= m <= 5402; self-edges make the answer NO.

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