CT56476

The Two Guilds Beneath Winterholt

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the snowberry thicket of Winterholt, Corwin the log keeper keeps careful count of the tunnels. Map a faster supply route, every figure matters. 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 <= 2886; 0 <= m <= 5772; self-edges make the answer NO.

Example 1:

Input: 2035 2202 1048 1456 1240 1810 400 582 399 1415 323 1133 154 480 462 1570 580 808 499 2011 1417 1869 280 1336 410 1618 175 918 773 1370 67 1642 99 1681 1724 1739 458 1243 75 1792 444 1625 930 1485 572 818 820 932 888 1409 500 1269 1129 1660 1527 1550 193 1654 373 1863 732 1232 312 1192 635 1714 95 1099 1473 1942 705 937 1071 1206 151 579 654 787 358 1475 772 1194 431 1354 240 1673 276 645 78 1629 25 1728 734 882 298 1118 692 1472 1095 1872 931 1872 177 1909 762 1279 1242 1686 592 1785 1202 1354 288 1169 128 1444 590 721 357 986 687 1189 101 1558 233 615 331 1229 679 1523 342 519 1172 1692 438 1505 119 1809 1524 1885 45 1525 7 559 1181 1914 1304 1430 510 948 625 684 14 307 338 787 670 703 408 785 75 1699 830 1105 514 1425 24 154 1109 1660 309 1526 565 1662 1377 1821 89 271 441 1325 1027 1315…
Output: NO

Example 2:

Input: 1881 2370 247 1287 499 642 819 1845 453 1839 457 1722 286 372 324 1290 63 986 592 1025 162 696 535 1687 703 1444 238 1526 739 942 900 1821 426 1719 962 1261 627 1597 1211 1227 1069 1796 886 1456 613 999 476 978 181 1383 61 1634 240 774 377 706 320 378 1160 1333 810 1637 20 1608 858 1860 873 1586 27 402 564 1555 699 855 910 1691 450 1877 987 1793 170 721 633 1659 332 802 446 1334 1006 1185 982 1668 208 671 1580 1695 717 1404 204 519 683 1335 118 270 172 1627 360 1650 749 1000 222 793 186 647 129 894 1191 1821 271 1341 1151 1276 463 1669 250 767 252 1020 315 388 541 945 274 850 550 790 338 666 781 1128 637 1698 1394 1757 264 1059 498 1129 119 613 1017 1225 201 1723 397 916 525 1025 40 963 464 1819 267 662 54 1032 704 1516 840 1532 689 1520 243 265 773 1338 216 1322 558 1746 31 1529 63 330 11…
Output: NO

Example 3:

Input: 1815 5203 1 2 2 3 1 3 96 1537 657 1653 701 941 338 1016 749 1802 182 1317 423 1254 1062 1234 705 1007 1379 1520 557 839 116 665 601 687 370 721 1226 1762 100 1651 343 1026 1406 1602 1005 1604 581 1741 493 808 70 1034 961 1308 795 1285 417 976 488 1193 24 612 530 602 1360 1735 295 1589 419 1045 1350 1440 493 1703 557 1671 466 1160 1467 1801 44 1786 59 1599 150 662 71 1782 616 1654 410 1138 168 229 142 1177 328 892 460 1646 77 546 285 1412 544 1457 132 1089 1019 1745 155 793 1009 1198 278 333 1296 1353 1523 1802 148 550 671 832 659 1654 347 1449 533 1222 579 826 38 1403 1009 1356 637 962 133 1727 590 1548 115 535 283 1772 1334 1479 785 1162 586 1405 1037 1733 1278 1752 465 539 44 1209 1458 1802 122 1294 515 1198 1596 1634 499 597 1104 1298 899 1485 1147 1785 1011 1043 842 967 215 835 577 102…
Output: NO

Constraints:

1 <= n <= 2886; 0 <= m <= 5772; self-edges make the answer NO.

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