CT57460

The Two Guilds of Mirrormere

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the lakeside town of Mirrormere with crates of routes, and Lara the dispatch writer must account for every last one. 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 <= 1966; 0 <= m <= 3932; self-edges make the answer NO.

Example 1:

Input: 118 3509 21 50 62 71 35 50 35 106 88 108 16 112 17 104 41 117 35 70 26 101 21 70 50 89 19 59 26 65 42 91 21 69 7 111 68 87 3 82 7 36 62 93 17 116 31 49 33 57 97 102 1 85 35 94 45 71 29 30 64 77 76 110 22 77 46 91 79 110 56 77 54 91 53 104 56 78 12 96 2 16 39 107 16 98 19 42 38 104 44 98 49 116 56 96 6 18 20 60 31 42 41 73 8 45 65 88 9 23 6 54 79 90 28 118 30 88 73 79 30 44 14 17 1 72 80 89 52 64 85 101 20 65 42 95 18 118 25 32 18 69 77 92 41 85 35 36 40 87 27 89 18 115 50 105 6 96 44 59 53 99 30 117 34 85 94 116 62 116 68 110 107 112 93 94 39 90 1 40 47 58 18 100 86 93 55 62 2 113 66 102 19 67 4 87 1 17 55 72 41 96 27 79 1 33 12 61 69 74 103 108 16 115 62 83 16 73 13 114 50 58 95 103 23 83 51 88 11 87 10 53 30 49 42 81 10 29 13 76 18 31 12 108 15 77 81 84 22 50 1 61 4 67 37 73 13 32 69 89 …
Output: NO

Example 2:

Input: 1734 1810 502 1308 34 254 51 1356 1119 1641 1004 1458 338 1002 688 1027 206 858 256 932 48 1582 351 976 300 749 346 447 1084 1530 16 339 1137 1166 428 1388 534 1088 830 1190 552 1357 20 653 65 1659 42 414 273 1008 841 1139 514 615 294 871 193 693 529 667 151 1711 562 1179 765 1484 300 712 774 1153 66 343 1111 1448 580 733 402 493 75 1708 227 1607 951 1277 80 576 350 1456 933 1713 752 1554 217 523 516 1164 382 1692 332 450 765 781 400 785 1038 1552 364 583 672 1163 788 1208 551 792 242 520 1473 1639 69 1470 337 1571 1638 1731 1372 1554 427 466 748 948 1022 1148 1400 1527 438 1619 84 1075 475 1310 640 1256 719 1279 26 1437 1539 1658 1328 1461 726 1391 50 1490 833 1677 326 911 797 1373 716 828 300 1710 393 1418 270 869 969 1624 1426 1570 106 235 151 389 43 119 601 1454 859 899 816 1530 332 12…
Output: NO

Example 3:

Input: 1906 658 64 913 480 1610 555 925 616 1102 168 931 49 1761 326 691 13 1472 1086 1467 1637 1675 485 1344 77 1699 1148 1456 219 982 1556 1580 1389 1616 384 1819 1440 1722 630 1792 278 1216 126 1775 68 974 461 923 1209 1700 662 958 1255 1399 1104 1314 21 538 280 1115 238 519 199 550 1449 1723 822 1177 27 607 33 1186 75 1704 114 392 803 1260 427 1231 294 1537 273 714 1258 1438 1441 1692 1199 1513 651 1209 786 809 552 1117 1400 1533 287 1451 1054 1714 631 1541 843 1539 87 1513 590 1182 200 1251 305 1591 617 1125 332 669 185 240 478 658 774 1640 975 1090 983 1383 1290 1738 47 279 461 719 53 1840 596 1158 469 1508 481 824 742 1498 494 1099 909 1076 1736 1885 224 1655 466 988 1711 1736 1402 1470 593 1193 4 493 217 1155 114 476 437 611 735 1410 1416 1648 80 957 271 1795 752 1466 297 449 652 1401 614…
Output: YES

Constraints:

1 <= n <= 1966; 0 <= m <= 3932; self-edges make the answer NO.

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