CT60362

Paige's Ledger of bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the desert outpost of Sandspire, Paige records each bridges in a worn leather ledger. The guild wants answers, not guesses. 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 <= 1607; 0 <= m <= 3214; self-edges make the answer NO.

Example 1:

Input: 910 2059 72 807 287 395 181 481 616 892 254 260 97 186 81 112 277 562 429 811 8 18 389 841 84 783 207 840 475 628 67 83 296 863 771 875 130 190 85 398 372 853 5 103 667 889 129 440 145 626 523 878 126 440 28 373 88 230 299 566 22 862 101 770 233 245 283 295 298 837 189 615 134 850 186 765 701 718 337 587 9 416 158 791 729 802 11 423 625 704 392 698 279 418 324 361 225 290 186 230 655 730 306 629 122 432 382 405 203 437 694 826 40 400 27 861 633 842 405 794 761 837 283 419 295 537 238 730 251 727 458 718 113 209 80 530 335 882 361 373 326 677 282 686 292 803 246 807 117 888 89 364 159 694 80 744 258 766 105 591 253 315 267 463 388 778 358 830 76 862 279 630 75 342 13 94 180 697 14 586 576 792 290 378 323 547 643 830 515 900 474 504 74 390 539 810 517 783 173 206 194 444 475 497 189 858 721 …
Output: NO

Example 2:

Input: 761 2757 1 2 2 3 1 3 58 714 289 678 116 546 544 731 99 573 346 498 572 662 77 720 214 423 178 437 530 647 113 473 475 574 80 755 270 304 185 727 542 571 256 351 192 333 8 338 221 413 105 719 20 33 101 120 10 480 251 265 267 420 101 305 450 485 175 511 476 517 302 578 264 726 57 448 313 543 25 487 180 718 512 517 428 719 295 672 159 752 179 735 271 480 294 623 455 603 5 614 415 625 126 169 13 343 4 515 7 730 34 680 91 243 216 262 206 503 568 732 43 743 438 478 68 126 60 612 272 464 599 744 446 505 138 715 150 182 201 468 384 458 287 749 264 758 5 254 350 493 95 383 45 227 182 746 412 577 470 625 168 756 105 287 12 461 166 439 462 534 110 569 253 608 117 372 276 703 406 686 334 527 126 622 160 572 64 738 342 748 682 722 100 183 176 419 90 407 175 619 352 583 17 409 525 597 436 704 369 565 37…
Output: NO

Example 3:

Input: 1425 1283 673 1348 949 1218 272 811 159 202 255 847 654 1193 951 966 266 567 577 1318 153 874 433 1027 731 1000 397 1097 300 1197 554 1002 428 445 759 1259 787 1341 145 333 478 1282 472 1181 331 511 447 1109 256 1324 784 1063 41 1004 1226 1338 269 1175 743 1140 627 677 290 1294 809 1178 194 1021 272 1237 816 1133 88 535 752 1378 252 598 35 109 1050 1180 515 996 655 1423 346 1298 1010 1128 546 678 114 920 240 987 252 648 454 915 319 1009 580 1304 135 855 27 142 593 1255 384 400 105 1107 178 1334 701 915 242 1201 487 1154 42 745 121 412 120 762 956 1204 473 858 665 1312 744 1411 746 1054 799 1162 661 1110 24 379 19 856 83 691 193 532 386 1351 529 1357 461 1177 1244 1388 601 1269 677 1045 689 1324 745 1186 257 1142 374 1013 615 1235 617 758 153 978 35 1278 794 1340 206 1323 130 1128 887 977 5…
Output: NO

Constraints:

1 <= n <= 1607; 0 <= m <= 3214; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Paige's Ledger of bridges - MEDIUM Coding Problem | CodeTikki