CT53025

The Thornveld Two Guilds

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Jessa found an old ledger of canals in the shed attic at the acacia flats of Thornveld. 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 <= 3158; 0 <= m <= 6316; self-edges make the answer NO.

Example 1:

Input: 1163 1718 164 684 768 1035 294 546 162 838 411 965 511 1055 244 628 91 543 400 893 939 1095 461 764 465 608 87 912 130 195 138 146 673 758 305 956 466 1052 119 838 725 817 397 1007 173 723 270 1019 1052 1086 42 473 7 945 83 173 350 945 341 572 723 1017 288 898 459 765 192 348 891 970 709 1019 498 819 824 1072 258 505 348 820 69 815 693 736 529 1038 366 824 22 1074 573 761 378 835 233 1147 697 1041 249 547 68 279 353 494 327 848 479 634 161 327 550 743 14 362 940 1157 60 283 83 301 655 842 846 1158 690 702 5 566 238 446 932 1124 925 969 92 272 233 890 257 686 291 546 414 550 392 925 432 435 442 980 48 914 117 1019 176 892 438 676 388 943 801 1056 338 412 185 552 112 528 6 526 302 320 830 946 142 1026 85 352 284 1155 545 990 195 949 192 473 392 1099 843 902 268 862 609 719 413 835 689 773 17…
Output: NO

Example 2:

Input: 1829 4910 148 1227 55 479 845 1058 773 927 891 1430 417 1665 941 1149 238 448 131 1337 1114 1704 349 957 165 993 538 1762 364 1737 1797 1813 425 1159 636 1034 349 1128 47 1698 687 1141 208 278 448 771 35 1204 670 1603 1587 1767 194 799 1013 1484 875 1494 770 999 1105 1739 980 1823 943 1175 424 996 343 1815 451 1037 1695 1779 414 1756 231 1787 75 1470 850 1178 880 1698 331 1601 562 1627 456 1514 1141 1206 33 1244 1077 1328 1166 1809 753 1388 351 1788 547 1528 46 1112 358 372 169 817 443 1487 502 1502 22 939 1028 1039 470 1739 623 1304 461 987 847 1225 174 1191 418 615 168 1375 467 530 1062 1140 592 699 56 149 6 840 333 1542 705 813 505 1825 336 1581 640 1085 219 1776 1028 1810 532 1505 343 1674 701 1398 230 349 1018 1336 1482 1680 1671 1754 357 1772 570 1142 100 1817 1249 1785 1350 1664 188…
Output: NO

Example 3:

Input: 948 5889 1 2 2 3 1 3 583 838 261 662 404 884 339 828 750 835 7 216 843 916 437 511 179 546 175 880 202 850 595 615 292 930 162 246 342 667 449 751 331 905 148 246 657 667 386 613 105 152 404 526 247 803 627 690 187 671 221 396 365 835 429 947 238 755 132 359 139 413 344 586 371 453 24 446 229 473 89 662 256 809 145 367 570 594 730 776 96 203 515 584 189 829 747 923 289 915 216 945 70 447 200 883 392 596 65 528 536 672 17 902 268 293 289 718 2 862 511 827 7 455 298 578 180 350 320 872 75 824 707 877 242 311 155 621 503 641 572 751 766 863 68 632 500 697 469 725 230 515 299 365 657 662 758 799 152 560 49 257 130 733 198 826 561 565 14 539 582 841 550 589 759 912 60 738 578 782 512 803 816 851 116 499 182 669 383 719 341 448 408 900 62 552 307 390 787 921 443 580 333 903 338 791 415 528 411 6…
Output: NO

Constraints:

1 <= n <= 3158; 0 <= m <= 6316; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
The Thornveld Two Guilds - MEDIUM Coding Problem | CodeTikki