CT47771

Keeper's Ledger of bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the tundra station of Whitesnow, someone must forecast next month's demand. This year the task falls to Keeper, armed only with the bridges register. 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 <= 2786; 0 <= m <= 5572; self-edges make the answer NO.

Example 1:

Input: 2268 4488 980 1293 56 2164 1761 1978 91 1871 1850 1871 122 1149 1371 2040 197 2107 337 1000 786 1356 169 2257 372 1956 618 1795 363 1086 733 927 160 914 801 1087 132 1025 537 1349 1207 1644 633 2043 680 2099 827 1683 238 368 22 1303 104 1085 179 327 280 1254 528 858 1331 1972 385 2256 986 1585 1180 1872 744 1453 800 970 1051 1506 580 2202 430 1339 1127 1294 1206 1310 480 921 1403 1610 1107 1171 532 2185 856 1725 611 1012 897 2266 640 1517 319 1215 571 1123 221 1307 100 613 703 794 1681 2100 1448 2024 1561 1579 610 1023 1 1581 1740 1804 785 1756 1163 2159 620 942 422 1238 1292 1932 941 1935 685 836 309 1055 1299 2222 1053 1657 1475 1516 521 845 469 516 1689 1916 1076 1789 1686 1720 2183 2213 69 2048 1601 2048 996 2029 44 1767 2 1774 1370 1880 1347 1459 660 1825 2035 2059 872 1547 907 2095 4…
Output: NO

Example 2:

Input: 1583 5211 167 1134 59 479 871 1348 276 1470 1340 1441 1016 1569 387 1456 618 1228 520 926 273 1141 200 1225 47 142 438 567 984 1106 197 892 39 1526 955 1217 8 185 813 1147 191 1217 219 468 162 1574 629 654 540 1320 401 1010 341 680 320 877 780 1180 379 1197 859 1182 1064 1556 206 540 190 335 386 887 255 1507 1435 1541 194 629 158 288 164 684 117 1513 117 1397 26 146 1351 1422 385 468 1275 1360 118 513 122 642 221 533 421 1212 491 820 562 781 336 1243 301 1185 779 1209 117 344 1225 1530 505 749 451 1332 680 1044 1371 1506 723 1574 1061 1263 823 1554 670 1399 202 1513 527 1290 327 1484 1205 1330 832 970 1191 1260 943 1375 477 1039 277 1464 296 959 415 682 664 884 883 888 273 1429 94 666 536 1438 13 461 297 1202 441 1369 347 976 228 758 705 1513 1141 1240 959 1386 594 1182 168 507 1447 1458 6…
Output: NO

Example 3:

Input: 1039 1837 1 2 2 3 1 3 369 744 609 1002 497 895 950 984 429 747 56 982 224 245 786 894 748 914 10 622 690 866 484 844 229 605 349 460 803 1025 243 867 49 524 180 1023 128 736 148 265 197 567 328 909 103 291 811 913 386 480 227 940 538 664 258 979 150 226 62 459 183 1011 573 633 163 710 776 823 84 1013 502 937 517 917 706 988 564 930 707 924 500 917 271 1020 314 708 489 643 175 337 146 354 455 664 181 747 648 778 327 368 293 354 332 381 41 382 41 846 215 397 391 656 407 424 787 840 228 411 638 987 329 997 32 883 131 373 355 707 800 1039 82 828 127 242 384 968 722 749 132 754 718 996 555 674 4 291 579 777 104 778 424 843 178 639 36 222 151 417 56 213 465 851 691 932 130 778 105 857 28 799 646 981 181 502 269 551 12 203 56 706 596 1016 847 870 144 705 758 892 263 312 12 809 573 909 5 87 209 74…
Output: NO

Constraints:

1 <= n <= 2786; 0 <= m <= 5572; self-edges make the answer NO.

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