CT58891

Wade's Ledger of canals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Wade found an old ledger of canals in the boathouse attic at the fox den of Rustwood. The margin notes pose a precise question. 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 <= 2538; 0 <= m <= 5076; self-edges make the answer NO.

Example 1:

Input: 1690 777 45 1293 1117 1453 5 294 1050 1193 1205 1431 467 1311 670 1343 647 1646 297 1382 588 1524 277 1366 941 1602 72 1087 791 1446 815 1185 1063 1193 1072 1105 6 1238 1130 1234 973 1034 353 946 864 966 147 653 1349 1625 571 955 200 1569 1232 1316 962 1588 144 635 117 555 935 1572 1142 1425 550 970 175 1226 494 1110 899 1068 423 1094 202 1250 315 1026 815 1458 112 1428 1494 1609 663 1120 125 1510 145 1440 968 1602 698 1684 452 1424 383 1038 762 1347 400 660 16 1215 287 328 326 1390 77 1093 599 1412 421 733 1260 1677 315 1570 50 598 596 1411 172 285 598 1292 1064 1509 1016 1241 278 611 333 1563 56 1272 546 791 685 1044 117 170 811 953 26 1657 285 360 49 1669 619 1621 484 954 608 1471 327 1169 844 955 34 794 724 1260 1146 1635 156 582 1207 1458 397 1624 104 1264 416 663 406 792 5 1205 185 4…
Output: YES

Example 2:

Input: 1995 1457 407 1351 770 783 101 1574 703 1590 237 1015 778 1503 1280 1495 876 1470 295 586 453 988 646 1126 932 1808 465 1213 215 999 97 1279 1439 1930 1134 1754 1104 1649 895 1585 3 1642 656 803 271 522 612 935 971 1582 763 1897 334 1053 1742 1872 190 940 153 1130 1475 1735 600 783 117 1331 197 1774 415 771 839 1630 913 979 673 1034 1502 1984 664 1795 275 1738 64 1596 88 1391 170 915 1137 1977 1082 1295 334 363 13 164 1072 1250 5 359 500 920 1248 1880 675 1494 693 1991 670 795 957 1768 1195 1987 149 1719 328 1598 949 1279 511 1159 1 794 417 1151 438 976 47 753 139 629 471 1416 183 678 580 1162 721 1497 1382 1924 990 1951 1607 1638 76 1925 830 1495 487 1095 935 1092 27 320 753 1621 1354 1602 897 1031 1338 1889 664 1033 238 1844 1320 1558 362 380 878 975 1570 1684 303 1612 985 1721 998 1420 …
Output: NO

Example 3:

Input: 1898 1573 140 188 330 1583 307 1185 291 1781 399 517 215 501 24 428 652 1250 1541 1690 236 1339 304 995 1195 1536 1435 1554 733 1082 455 759 13 93 1046 1460 207 1406 1035 1513 202 1021 362 1165 537 678 83 1255 609 1221 298 1847 3 1540 1106 1349 465 809 138 690 234 642 194 1496 376 539 119 1206 398 1845 696 1146 85 1200 216 1648 12 467 563 1666 153 1265 788 1576 711 1125 282 693 1335 1531 510 1860 166 1595 727 1606 536 1886 1210 1258 375 1897 403 1534 804 1841 308 1561 366 953 174 1552 552 1325 569 766 933 1862 970 1863 177 711 172 1569 492 623 1183 1595 109 1419 1291 1741 304 1387 365 572 437 1807 892 1383 1175 1378 935 1224 974 1374 466 1884 791 1303 621 923 608 804 236 985 1238 1753 1268 1452 34 1300 246 1646 5 70 307 1313 224 1564 784 1310 391 1518 174 921 1143 1560 383 1453 947 1367 20…
Output: NO

Constraints:

1 <= n <= 2538; 0 <= m <= 5076; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Wade's Ledger of canals - MEDIUM Coding Problem | CodeTikki