CT60136

Admiral and the Two Guilds

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the ferry landing of Crosswater opens only for a perfect tally of roads. Admiral 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 <= 2966; 0 <= m <= 5932; self-edges make the answer NO.

Example 1:

Input: 2650 4860 2238 2389 1087 1975 815 1330 87 243 2152 2521 1106 1774 1138 2366 573 1428 559 1465 2025 2152 911 2575 2095 2404 110 2112 2342 2564 694 1843 320 2501 1876 1922 297 864 403 922 928 1234 1875 2378 852 2313 592 1276 9 136 398 2426 238 2418 1664 1969 742 1446 1260 1643 326 1671 1364 2196 248 589 792 921 653 1782 688 1085 142 2245 1090 2284 362 884 410 1879 1180 1874 22 1608 94 2365 16 179 800 1625 1803 2345 1724 2218 570 1922 1412 1746 315 2494 2418 2598 575 780 1247 1464 1166 1523 281 1660 1961 2009 20 291 696 1023 119 584 2124 2343 980 1047 45 2372 809 1382 1071 1470 842 1580 14 2051 427 2246 181 328 1040 2226 189 943 904 2163 696 2274 662 1141 1368 1792 611 1332 2048 2575 650 1467 1647 2112 2558 2637 906 2100 233 1032 202 1316 1186 2232 603 1487 28 526 2482 2548 149 2013 1627 2184…
Output: NO

Example 2:

Input: 2952 1671 1 2 2 3 1 3 990 2105 175 2949 303 2771 1227 1761 1530 2750 1132 1860 885 1590 1124 1369 2482 2679 380 1991 140 1518 530 2579 848 2109 2394 2776 1231 2621 749 1315 360 1772 301 1133 997 2601 460 1956 1163 1224 1213 1580 398 2892 956 2672 938 2610 475 2021 2298 2734 164 2254 11 2000 529 2470 533 1288 1115 1441 792 819 907 2528 2009 2033 1817 2177 722 1116 677 1516 160 860 637 1837 504 654 924 2195 1897 2729 906 997 63 978 47 485 1112 1701 2070 2750 93 163 668 2501 538 898 287 335 2342 2911 341 364 236 777 353 2496 1296 1324 2407 2441 413 1224 531 1153 94 830 856 2004 2268 2877 2054 2256 1587 2397 1284 2627 1105 2403 126 1126 126 2274 822 2185 1389 2078 583 1663 2662 2743 256 2786 1175 1936 604 1253 514 1021 685 1877 602 1039 2109 2765 996 2379 225 678 169 996 1000 1513 2183 2436 70…
Output: NO

Example 3:

Input: 2873 2904 17 1683 2462 2645 220 1152 337 671 539 1496 119 1578 1058 2315 361 2684 2467 2626 1479 2069 998 1415 572 2556 2010 2688 28 1269 768 2732 658 1750 662 965 922 1972 1456 2591 174 757 1524 1933 391 1728 2371 2648 720 2722 2532 2841 1124 2328 1390 2679 1244 1862 274 2649 621 828 1398 2675 543 1223 462 815 478 1599 461 2770 495 1471 1351 1591 494 2432 680 2549 493 2167 701 1559 1789 1980 179 1965 1905 2471 52 1061 565 1320 115 1132 283 852 638 970 664 2576 1488 1720 580 2334 1143 1171 82 1243 419 2779 2089 2612 17 1366 741 764 62 766 370 1256 1277 1854 1047 2476 548 647 1788 2606 1713 2100 772 1231 1303 1968 1359 1468 73 2289 1291 2584 447 1238 1211 1804 72 2800 200 2033 943 1383 1285 1997 900 2686 618 2792 615 775 13 559 895 2111 1958 2421 607 2483 58 1952 231 1611 902 1572 199 1048 …
Output: NO

Constraints:

1 <= n <= 2966; 0 <= m <= 5932; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Admiral and the Two Guilds - MEDIUM Coding Problem | CodeTikki