CT46817

Lothar's Verdant bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The cartographer Lothar has been asked to schedule the next expedition. On the desk lies a long table of bridges 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 <= 1415; 0 <= m <= 2830; self-edges make the answer NO.

Example 1:

Input: 986 2219 1 2 2 3 1 3 186 787 665 688 459 914 241 528 661 874 28 650 87 252 388 856 351 968 53 330 145 163 644 986 159 751 365 386 689 780 349 818 170 213 412 856 233 667 689 795 345 361 105 798 797 963 65 856 437 513 469 946 350 627 128 135 218 663 261 780 389 956 546 572 15 208 663 960 171 270 360 388 220 236 332 519 535 929 5 60 577 792 171 377 487 551 420 892 177 590 197 286 354 651 375 716 86 140 211 964 697 723 17 743 11 669 152 896 450 476 128 421 88 862 74 121 25 35 709 850 57 88 722 768 216 874 46 846 616 764 19 945 477 975 97 277 10 434 490 768 340 917 296 305 421 770 310 769 85 879 7 252 590 829 298 426 616 724 32 256 5 937 658 905 4 749 367 794 8 113 268 481 252 460 200 597 664 736 199 453 554 661 117 605 444 494 66 228 250 872 422 569 4 39 760 924 378 568 787 912 691 771 886 94…
Output: NO

Example 2:

Input: 939 1841 1 2 2 3 1 3 350 582 762 849 410 656 14 212 319 771 85 605 81 548 206 659 288 855 55 334 151 575 239 877 487 597 103 374 231 380 475 937 466 763 323 702 6 201 443 868 382 673 19 232 27 819 686 929 290 925 258 806 514 823 313 782 486 866 136 567 350 533 581 662 259 832 35 179 290 316 108 752 57 409 129 543 195 626 444 696 241 535 27 194 426 460 3 847 165 595 108 726 280 414 198 727 494 687 629 632 887 900 61 137 319 465 188 239 452 862 699 810 88 547 741 880 89 715 466 852 68 147 190 816 147 160 411 935 436 448 247 857 411 910 149 540 784 927 270 555 41 262 196 559 172 266 299 554 39 236 157 762 588 938 871 912 495 933 199 345 750 876 344 393 133 727 167 406 120 169 258 645 179 273 112 778 301 506 548 641 83 490 635 640 766 871 643 929 599 862 519 791 500 603 416 692 687 715 444 816…
Output: NO

Example 3:

Input: 1056 53 13 567 552 695 24 874 394 488 366 682 338 663 295 504 932 934 136 306 184 607 138 689 245 850 674 893 317 676 508 768 120 1042 489 934 23 303 699 1031 378 393 634 764 444 639 534 593 558 842 686 793 952 964 256 659 98 204 558 773 540 731 269 639 235 553 371 814 44 741 274 287 344 841 786 970 114 899 765 939 129 811 823 837 196 388 155 234 578 649 306 484 127 178 1005 1025 479 1048 17 354 146 576 488 732 202 514 742 1042
Output: YES

Constraints:

1 <= n <= 1415; 0 <= m <= 2830; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Lothar's Verdant bridges - MEDIUM Coding Problem | CodeTikki