CT52973

Miller's routes Two Guilds

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Miller runs the brewery at the port of Emberfall. Today the books show a list of routes, and the numbers must be worked out before sundown. 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 <= 3307; 0 <= m <= 6614; self-edges make the answer NO.

Example 1:

Input: 1739 3058 286 1214 455 1512 1244 1309 1274 1675 390 1115 242 1177 1294 1397 479 699 587 1091 814 1525 537 1069 866 1268 1285 1568 322 335 324 1122 58 1356 936 1459 1104 1462 150 937 806 1492 838 1133 896 1658 273 577 865 1292 781 1062 237 985 1411 1571 811 1466 183 349 417 753 312 315 1141 1250 895 1603 533 1728 719 836 699 1099 1296 1656 438 1369 188 1121 150 624 1327 1374 1393 1526 569 1130 457 817 1272 1552 1070 1590 999 1708 188 605 844 927 613 1716 725 1030 412 1546 405 769 138 1185 507 1672 1303 1572 269 1708 614 880 231 1515 394 1248 1278 1350 163 1274 1600 1728 936 1375 307 434 1060 1722 173 388 92 334 513 599 1354 1571 529 1580 1364 1651 64 1590 210 1143 1051 1657 802 1633 366 1174 533 1736 1072 1645 1109 1376 213 247 742 812 77 1505 1286 1564 1349 1386 105 437 440 1051 482 564 87…
Output: NO

Example 2:

Input: 2466 1299 711 2057 946 2166 1231 2001 283 891 171 638 197 725 220 412 146 2176 1420 2094 252 2405 2005 2076 1152 2122 963 2029 653 1491 1666 2364 429 2122 1584 2369 142 1050 653 818 526 1442 74 1155 1673 2287 1037 1877 612 1100 34 675 335 1191 106 1308 1808 2429 1425 1431 245 1280 1249 2216 59 832 283 2188 1073 1312 128 377 104 506 1848 2432 265 865 1802 2175 2371 2422 370 1492 185 573 768 1224 270 1862 873 1381 1077 2194 1925 2098 211 625 965 1810 178 1332 1519 1672 1000 2203 1756 2031 397 1241 1300 1954 204 1957 101 2411 743 1478 631 821 1044 1761 854 1101 753 1094 1028 1672 1044 1792 793 1541 940 2456 573 1950 2157 2338 198 1041 3 1359 2196 2364 1651 2112 328 2336 1577 2361 279 1731 901 2351 715 1624 1086 1354 293 1057 209 558 123 1849 1786 2320 2 1297 1660 1881 899 1826 569 1710 680 85…
Output: YES

Example 3:

Input: 3029 2953 77 1343 1252 1584 861 1675 2244 2590 227 1524 1467 2253 1309 1607 931 2391 1586 2053 2608 2699 1828 2237 10 2341 1088 2375 2289 2705 787 1715 1807 3012 1609 1805 177 399 356 1163 1918 2939 203 249 369 1557 541 1651 1114 2889 560 933 436 1936 1121 2971 664 1400 1040 2325 2056 2078 2298 3023 2150 2648 813 2733 162 1601 2563 2807 1231 1979 2135 2505 1291 2337 466 2657 151 1128 1074 1850 2149 2776 601 2571 1294 2405 1373 1659 74 2947 1734 2683 1737 2319 191 2977 1594 3018 494 878 1934 2912 894 2062 279 2997 839 901 86 745 1318 2423 1758 2635 1987 2220 1119 2960 718 1823 102 644 726 2910 535 2978 38 2545 1236 1985 1006 1574 381 1803 2811 2884 2147 2674 600 774 1086 1888 69 492 1345 1399 1393 2364 417 513 74 2565 69 1810 306 2636 574 913 2203 2357 618 987 2150 2760 2005 2383 40 579 215…
Output: NO

Constraints:

1 <= n <= 3307; 0 <= m <= 6614; self-edges make the answer NO.

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