CT48615

The Celestial Two Guilds

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The quartermaster Marek has been asked to chart the migration season. On the desk lies a long table of tunnels readings. 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 <= 2390; 0 <= m <= 4780; self-edges make the answer NO.

Example 1:

Input: 1541 2478 597 1282 451 900 367 849 625 1381 562 1179 105 361 669 1366 84 1435 415 1026 100 685 929 1274 77 1003 265 1310 108 510 505 980 165 1236 583 889 1166 1531 971 1189 641 939 173 248 312 839 529 1472 731 1358 203 1013 508 815 171 1159 305 1107 277 1470 461 518 644 1265 313 1400 851 1059 491 695 628 969 1041 1403 285 1188 281 474 405 815 114 305 433 1335 321 887 30 473 407 1339 739 878 304 1042 401 472 330 1360 1330 1438 48 787 505 1052 200 343 4 917 111 251 522 830 978 1303 478 924 526 1140 767 881 851 1080 236 1271 627 1001 54 215 795 1195 1031 1035 875 1285 45 662 250 272 173 1211 260 1204 659 907 337 1466 571 1469 227 503 203 762 626 1358 31 92 411 616 558 1363 226 380 788 1481 864 1242 91 1428 142 1370 631 1391 471 1290 731 787 1185 1344 410 542 973 1403 1188 1524 92 652 368 1008…
Output: NO

Example 2:

Input: 1838 413 1401 1592 704 1180 250 1757 725 1401 1517 1714 318 831 1006 1569 877 1436 116 1461 121 1634 1450 1649 400 1435 793 1418 514 845 729 1654 111 861 233 1229 704 818 161 660 241 964 673 1368 247 1627 887 1809 116 818 227 1050 661 905 859 1560 218 1376 82 678 192 771 266 996 183 940 1359 1578 555 1213 1716 1760 1340 1718 462 1129 1032 1368 604 1666 216 1099 751 862 316 1187 954 1557 778 1607 767 1629 748 1215 112 662 474 1108 412 1497 1098 1574 844 1195 630 1327 202 215 74 1554 871 1376 684 750 258 1273 607 1273 732 1644 925 1248 696 1411 1012 1431 980 1171 383 1742 143 522 1431 1709 60 1187 479 508 1461 1755 496 1808 767 1607 581 773 423 1070 590 653 1204 1414 557 774 357 846 1367 1658 968 1824 450 840 961 1429 106 1389 213 1475 485 954 1261 1283 829 1588 720 783 1283 1618 915 1477 12…
Output: YES

Example 3:

Input: 955 3954 1 2 2 3 1 3 458 926 760 866 220 794 109 197 151 590 336 704 250 825 252 616 761 934 400 856 594 621 422 778 115 620 567 904 363 427 362 914 178 937 412 872 206 555 406 840 232 371 279 773 579 848 29 449 551 760 405 632 170 490 325 879 96 424 321 952 140 282 56 169 42 43 232 530 423 524 114 754 317 365 261 407 605 786 247 655 843 873 576 777 133 597 1 680 297 382 56 421 476 489 23 762 8 306 458 878 229 320 142 688 574 902 24 804 328 368 563 808 311 725 113 604 449 515 690 823 830 938 340 363 642 787 656 680 143 647 314 492 832 860 688 940 622 950 407 909 55 347 278 803 31 215 105 206 274 723 704 759 239 248 74 721 243 580 96 953 90 735 231 254 686 801 34 726 579 807 331 616 181 953 309 634 248 671 581 895 58 443 78 612 262 822 41 203 56 444 676 891 307 849 293 546 187 409 701 722 1…
Output: NO

Constraints:

1 <= n <= 2390; 0 <= m <= 4780; self-edges make the answer NO.

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