CT60610

The Saffronia Two Guilds

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Zia the reckoner watches over the spice bazaar of Saffronia's stores of bridges. A careful computation stands between order and chaos. 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 <= 2639; 0 <= m <= 5278; self-edges make the answer NO.

Example 1:

Input: 1791 3525 1 2 2 3 1 3 784 1075 987 1565 1025 1216 624 1020 583 918 526 798 428 688 557 786 891 1205 414 1660 895 1371 248 1653 366 677 37 354 348 622 525 530 614 754 654 1401 592 1657 1016 1047 130 347 673 1563 1588 1693 989 1018 51 1296 120 1576 1148 1375 743 1751 1487 1603 1583 1608 189 590 303 1657 425 1022 490 883 1611 1674 509 714 817 1029 646 1413 592 1301 248 1596 1422 1526 93 1474 372 590 965 977 524 981 35 1185 1047 1188 507 1641 170 266 9 1551 433 816 681 1350 825 1360 1071 1378 92 1560 1113 1439 19 1387 31 45 1102 1367 938 1321 239 580 504 1131 656 1474 674 1615 454 1715 723 1736 778 1778 502 1596 500 1157 25 886 281 1070 258 1386 393 1186 297 1263 349 1201 1003 1630 407 431 773 1216 1041 1442 888 1685 9 1106 1199 1610 1143 1230 1463 1647 921 1010 509 1324 454 1184 712 1383 1097…
Output: NO

Example 2:

Input: 2496 523 1 2 2 3 1 3 225 1341 156 1010 306 2267 345 1958 965 2474 1563 2439 126 981 1320 1764 419 1775 311 2009 236 2288 104 1451 1066 2003 1779 2452 1617 2025 1319 1555 313 1685 1030 2446 382 1354 1190 2223 127 2269 943 2469 353 758 201 2109 128 2226 353 1786 72 1546 1447 2023 81 1828 1659 2036 2059 2462 1025 2351 630 1692 1918 2341 987 2041 258 902 1204 1248 294 303 1079 2309 673 1057 230 1853 1252 2042 1179 2004 1313 1635 1580 1952 1280 2063 209 333 1028 1310 946 1753 1077 2223 1130 1333 115 691 244 1716 1890 2325 1583 2398 1649 1956 1324 2416 77 1273 1101 1848 795 2488 2279 2394 1142 2164 146 1967 536 1237 1501 2462 1417 2417 341 2496 1209 1484 1522 2455 1135 2447 1521 2250 343 354 836 1984 418 1521 1644 2126 454 766 54 1591 133 2380 893 1668 1926 2195 1117 2197 172 729 810 2473 1645 1…
Output: NO

Example 3:

Input: 878 1608 657 712 533 819 270 819 284 655 109 333 159 370 83 90 136 696 79 621 508 716 2 231 18 158 13 626 58 512 274 333 406 740 93 145 112 120 139 256 40 499 617 875 54 489 415 819 512 614 100 401 135 178 301 321 444 550 237 849 78 121 130 753 310 694 100 835 20 632 195 341 38 521 207 812 223 555 117 324 106 222 121 745 294 556 567 670 263 271 302 604 677 754 386 634 657 782 520 636 490 798 708 851 112 821 537 674 216 535 577 769 336 623 520 719 209 426 340 456 181 201 170 221 257 858 85 215 479 802 340 692 205 611 132 315 407 422 237 381 354 766 78 313 101 450 754 845 107 115 121 720 47 326 78 256 102 731 787 836 327 525 120 785 157 263 274 592 301 322 89 388 370 739 115 848 100 766 600 709 153 437 743 856 164 709 226 761 170 224 80 386 40 537 726 878 678 828 698 838 362 678 312 715 114 …
Output: NO

Constraints:

1 <= n <= 2639; 0 <= m <= 5278; self-edges make the answer NO.

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