CT52610

Last bridges of Urmila

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Urmila inherited the timber yard at the crane marshes of Stillwater along with its curious bookkeeping system for bridges. Time to make sense of it. 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 <= 2828; 0 <= m <= 5656; self-edges make the answer NO.

Example 1:

Input: 836 3424 1 2 2 3 1 3 242 498 6 214 183 713 167 285 168 495 227 550 38 605 52 730 69 702 15 57 30 634 296 801 630 800 389 801 663 687 435 595 130 581 68 208 198 605 348 808 676 731 127 813 217 432 123 387 98 650 139 541 351 691 201 346 412 828 269 299 134 779 374 404 369 410 727 752 305 533 450 718 301 374 394 776 32 491 277 597 89 646 345 516 6 789 305 670 146 369 400 724 273 338 35 629 39 626 370 756 383 514 143 697 245 313 183 492 268 364 15 411 372 715 104 616 45 250 77 116 127 532 498 547 356 696 393 641 458 629 68 165 309 568 424 754 381 511 16 196 122 389 216 364 323 553 712 820 243 513 329 443 178 524 374 784 662 762 376 818 284 671 206 274 182 225 824 830 400 818 154 706 40 352 228 734 163 513 24 822 532 591 104 156 422 532 257 499 613 824 167 541 622 825 364 761 3 389 349 811 114 …
Output: NO

Example 2:

Input: 877 227 174 787 11 85 398 668 648 750 284 411 170 735 40 657 94 355 483 808 208 421 104 227 80 674 606 619 23 293 143 681 59 646 497 667 120 638 118 233 406 489 80 298 52 462 87 185 111 475 31 88 338 515 571 800 607 615 24 66 438 556 188 871 270 522 377 468 652 791 303 803 458 652 123 644 379 835 229 434 5 44 27 349 185 573 314 336 335 405 391 576 33 50 317 458 10 520 198 825 44 229 112 182 138 248 432 720 557 799 14 627 58 87 339 463 152 185 648 837 411 765 400 868 72 74 65 784 309 636 119 306 258 767 38 425 204 620 334 521 268 657 23 506 636 692 136 387 258 849 72 605 33 701 101 701 462 845 182 285 309 442 610 823 648 874 523 788 253 738 473 825 368 379 158 599 172 739 522 737 4 575 349 364 437 725 128 628 290 339 145 340 160 428 146 399 189 617 96 776 75 848 197 471 127 738 142 607 83 1…
Output: YES

Example 3:

Input: 2029 4763 476 1610 665 997 448 488 160 1429 1016 1432 71 1532 837 1226 1047 1483 394 1348 521 1710 337 1274 1046 1773 953 1867 767 1523 157 236 5 967 271 971 222 1145 165 248 615 1267 608 1415 730 1014 792 1708 172 1146 1263 1281 255 1396 974 1806 153 388 942 1648 328 1453 1544 1769 121 441 1637 1859 24 1370 784 927 545 991 623 866 341 1628 1045 1057 340 1389 478 1581 1022 1469 440 1852 546 1358 157 1747 608 1749 75 501 531 721 280 1535 392 826 504 570 941 1443 992 1995 32 1351 605 1459 861 1603 903 1506 237 658 191 208 377 1928 494 958 210 996 444 1730 617 1993 597 1261 312 1763 570 1543 933 1506 186 992 358 1987 1031 1956 563 986 337 386 1172 1736 942 1118 377 1585 1590 1603 420 2003 645 1063 198 1499 149 248 658 1306 633 1871 1429 1532 69 1157 116 1405 747 1618 955 1170 4 1241 951 1947 …
Output: NO

Constraints:

1 <= n <= 2828; 0 <= m <= 5656; self-edges make the answer NO.

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