CT35044

The bridges Two Guilds Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the thorn maze of Bramblecourt, someone must fulfill a tricky customer order. This year the task falls to Wren, 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 <= 2906; 0 <= m <= 5812; self-edges make the answer NO.

Example 1:

Input: 1718 2515 168 1091 264 640 1073 1402 130 659 303 867 273 1707 172 889 55 918 134 361 647 1072 327 1258 122 1396 642 1594 527 1405 1120 1680 501 935 539 1512 134 552 453 1358 400 1585 652 820 452 1532 851 1392 747 1048 364 602 1114 1139 228 920 1399 1444 1158 1361 1272 1359 649 803 670 768 58 1369 1399 1550 1605 1690 110 1202 1014 1171 406 1419 291 1640 1001 1268 1003 1515 1124 1570 848 927 970 1379 86 134 645 647 754 1411 1295 1658 79 93 283 812 37 1241 138 1635 808 1322 214 1084 376 424 421 677 530 829 680 1296 616 874 944 1205 752 852 1262 1557 817 1525 681 1556 973 1225 204 986 1091 1299 616 670 1186 1320 352 1580 472 964 648 835 461 946 683 1407 157 1566 1093 1222 474 1424 658 1282 891 1068 1392 1394 628 682 1013 1523 252 961 294 1233 866 1369 779 1476 159 1406 731 1641 68 656 542 1435…
Output: NO

Example 2:

Input: 1882 1235 1 2 2 3 1 3 1798 1819 1208 1566 661 1171 1338 1454 372 1491 981 1681 990 1261 984 1255 444 821 55 400 1308 1551 1195 1409 628 810 1219 1799 226 698 628 1770 31 1805 459 1010 1010 1137 1410 1505 255 558 1032 1539 1487 1811 367 1382 356 1435 380 435 616 1259 1247 1333 587 971 52 1421 697 1611 124 858 185 186 655 956 61 303 1145 1577 1141 1193 709 1843 1460 1575 375 471 1519 1869 100 961 610 945 1370 1395 863 1744 1273 1752 907 1181 587 843 527 1847 1405 1501 486 818 842 1227 683 1052 295 1064 73 1303 157 916 621 764 244 1595 320 1136 29 1228 195 639 754 904 1033 1407 145 891 470 1042 1732 1733 98 558 1392 1700 569 1650 273 1589 1832 1843 586 1387 1004 1762 902 1162 942 1043 315 762 212 1789 696 1475 1071 1673 381 1518 623 951 1408 1435 210 1499 1394 1514 1160 1873 1505 1765 479 175…
Output: NO

Example 3:

Input: 1461 4031 1 2 2 3 1 3 52 1028 667 1338 510 529 580 968 742 998 192 1317 64 726 33 958 954 1334 228 927 300 1166 875 917 437 1075 5 1422 77 1006 302 354 111 210 4 165 473 885 292 762 996 1403 1264 1442 907 962 1071 1271 506 1243 22 398 516 1353 358 803 828 970 67 269 122 135 447 471 216 857 1132 1201 75 299 1052 1076 76 1284 462 990 469 741 1347 1393 461 865 340 901 397 461 151 878 964 996 894 1030 553 1202 879 1246 135 718 77 827 1008 1248 519 1099 206 437 560 1140 1139 1317 489 1428 332 471 594 1209 201 494 467 512 491 1107 191 1125 1053 1063 574 1411 383 512 131 1092 557 719 147 1428 281 728 402 536 613 665 94 1141 641 1337 806 946 282 1078 1082 1279 610 922 42 1237 491 685 430 738 281 941 184 741 1024 1059 265 1250 195 1098 76 564 142 1105 1296 1446 613 1014 50 486 223 1223 681 893 1031…
Output: NO

Constraints:

1 <= n <= 2906; 0 <= m <= 5812; self-edges make the answer NO.

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