CT51673

The Two Guilds of Nacre Bay

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the pearl fisheries of Nacre Bay as Petr unrolls the day's manifest of tunnels. The tally will decide the next shipment. 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 <= 3260; 0 <= m <= 6520; self-edges make the answer NO.

Example 1:

Input: 2184 1284 1 2 2 3 1 3 702 1982 1670 1823 1119 1718 367 1652 1279 1763 27 1818 841 864 342 2064 489 1571 181 1301 1008 1618 69 1757 1096 2155 385 935 1552 1897 435 1162 370 1707 1027 1117 937 1579 822 2170 844 1870 372 1020 1304 1726 1268 1786 1795 1839 335 1792 1450 1907 526 888 1028 1654 535 1686 119 707 1077 1142 256 1370 1294 1528 538 963 708 985 270 1766 795 1385 651 1693 138 1347 179 954 550 1055 1680 2184 571 1898 456 1652 664 1433 1348 1853 976 1194 1680 1927 1440 1521 404 1329 61 1633 211 1894 473 1944 1238 1790 418 496 292 931 939 1535 72 587 422 456 492 1866 1511 1600 1009 1374 809 1314 322 739 242 1609 1444 1909 1980 2130 27 402 669 1718 806 1955 1269 1464 1411 1971 49 1095 1884 1998 1101 1554 137 1387 1801 1863 1369 1845 1865 1874 567 1797 1249 2119 542 716 1387 1990 1004 1433 …
Output: NO

Example 2:

Input: 2528 106 1 2 2 3 1 3 40 517 1402 2323 1295 1483 918 1165 149 218 241 2008 161 754 956 2183 291 735 391 1436 2429 2453 1131 1672 1176 1737 784 1107 388 1280 2172 2289 1609 1780 758 2397 1101 2316 130 2016 1971 2300 199 1360 114 705 856 1792 2110 2118 1628 2098 1434 2094 2094 2331 1562 1956 658 1529 183 838 1067 1209 609 2127 135 2161 29 2397 2073 2162 637 1733 1245 2439 1610 2403 603 846 1222 2290 243 1525 697 1763 1689 2020 170 1163 1312 2184 824 1557 1666 1756 846 1982 1166 1305 625 2425 725 1988 1724 2052 853 2364 1976 2080 94 1298 245 1707 147 413 506 2023 1597 2052 539 924 1539 2444 1219 2222 627 1839 665 753 483 2113 1308 2002 1138 1189 1076 1424 58 995 1528 2225 232 321 987 1358 430 2357 74 2247 565 1047 1515 2263 1498 1787 829 2001 255 956 20 2508 171 1442 161 560 874 1361 1610 1733…
Output: NO

Example 3:

Input: 2814 404 946 2398 280 499 1718 2021 852 1935 1201 2696 765 1642 2347 2422 1888 2024 345 1404 901 1359 797 1973 167 1569 459 2704 117 777 159 1539 1015 1802 280 1750 1507 2302 252 305 497 1000 317 2270 431 1164 698 942 1677 2363 498 2196 219 1662 2136 2514 1297 1393 412 1532 891 1553 580 1207 1496 1558 2033 2752 810 1113 1790 1840 1000 2259 1913 2326 397 2175 1702 1718 1242 1391 785 1608 936 1684 956 2500 304 1740 312 635 446 632 642 2609 959 1916 1696 2610 229 2247 1266 2527 643 800 2006 2111 2021 2477 810 2487 647 2707 325 1832 2032 2090 99 1502 1057 2219 78 1288 98 1570 383 1518 1771 2400 335 1906 257 2637 681 2785 1141 1607 2546 2562 1557 2098 1412 2218 766 1319 1845 2148 785 2256 610 1724 1332 2803 375 2626 1164 2120 171 2314 1805 2044 275 677 1558 2083 874 2086 300 1634 297 2406 8 991…
Output: YES

Constraints:

1 <= n <= 3260; 0 <= m <= 6520; self-edges make the answer NO.

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