CT60487

The Two Guilds at Briarthorn

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Maya runs the cellar at the forest village of Briarthorn. Today the books show a list of canals, and the numbers must be worked out before sundown. 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 <= 1955; 0 <= m <= 3910; self-edges make the answer NO.

Example 1:

Input: 1075 1660 1 2 2 3 1 3 98 780 281 539 40 1026 470 573 265 830 908 1045 849 854 394 1024 188 516 249 770 51 498 606 722 133 291 762 988 125 193 203 860 254 675 990 1053 26 1065 458 653 367 568 222 552 206 216 241 499 269 1073 439 877 218 942 31 276 811 894 197 517 76 794 414 1050 40 948 333 1056 772 1021 275 815 665 858 177 249 491 1036 91 170 567 1004 287 612 32 43 656 676 12 693 250 842 295 428 597 696 286 749 92 885 542 1012 485 783 327 579 599 791 19 612 179 342 472 605 73 276 66 903 215 514 371 552 283 1053 221 939 36 866 233 833 409 811 29 476 157 1037 185 1046 63 795 568 731 264 715 177 184 518 985 195 631 769 788 93 584 880 1020 548 590 123 715 988 995 63 1069 98 805 242 250 117 990 121 252 851 971 594 722 316 1012 304 522 165 632 300 364 665 726 570 1048 409 758 577 805 212 646 220 …
Output: NO

Example 2:

Input: 1639 2062 640 918 776 1256 944 1307 1201 1623 76 463 100 462 794 1119 368 397 619 1610 61 182 711 1439 928 1507 199 379 551 832 240 623 1386 1451 649 1593 398 1336 729 739 167 220 849 1291 556 1282 80 625 1132 1546 527 1119 125 535 608 1480 662 1512 948 1109 1209 1430 614 631 726 1292 479 980 337 1014 340 411 277 343 192 542 77 534 728 1574 742 778 181 951 339 967 853 1179 1248 1264 169 1153 431 863 1285 1434 136 881 1365 1624 217 256 383 1103 1157 1250 1341 1364 284 670 902 1492 945 1286 595 1002 787 1445 1257 1471 964 1400 805 1294 295 1192 673 1397 293 1002 210 1447 111 1236 1009 1577 593 906 1307 1466 1175 1576 485 803 261 1588 826 1436 188 247 528 840 456 764 634 873 155 225 1292 1414 245 554 407 1177 184 907 716 1359 15 146 191 826 450 825 39 191 203 212 702 1443 337 1438 317 1148 92…
Output: NO

Example 3:

Input: 1722 2473 1 2 2 3 1 3 387 391 906 1703 1242 1722 26 947 38 501 645 1716 5 1363 891 1570 1442 1570 455 635 726 1303 742 842 1473 1593 302 1665 848 1544 184 472 80 515 109 779 839 1599 521 694 341 1312 715 1597 1143 1162 615 1070 519 583 902 1646 518 841 295 533 213 1652 250 1059 588 810 1347 1538 257 908 657 1538 1010 1295 1480 1537 541 1637 1043 1267 502 672 15 894 693 1355 121 460 16 406 1649 1660 1226 1716 16 1028 589 1388 1389 1402 1166 1534 78 1477 1056 1095 814 1253 535 1464 731 1131 759 1238 580 1676 37 811 1127 1549 772 1211 1092 1623 74 209 1275 1403 184 1058 55 283 1202 1520 321 967 1074 1477 261 830 561 1040 577 1120 1171 1508 201 1593 386 461 239 1648 1076 1250 469 1146 1430 1510 495 721 738 1424 528 1684 205 1494 63 424 857 881 745 1358 518 653 371 1542 1071 1441 687 725 1 312 …
Output: NO

Constraints:

1 <= n <= 1955; 0 <= m <= 3910; self-edges make the answer NO.

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