CT49426

The tunnels Two Guilds Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Sahil runs the granary at the temple city of Sunspire. Today the books show a list of tunnels, and the numbers must be worked out before sundown. 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 <= 2301; 0 <= m <= 4602; self-edges make the answer NO.

Example 1:

Input: 2164 3215 1274 1287 1172 1514 347 909 1014 1783 264 2140 991 1672 1186 1555 1949 2144 1017 1473 375 622 565 1408 1154 2011 175 1223 1007 1288 1378 1456 1437 1996 963 2122 942 1939 795 1107 190 632 779 1472 344 1857 172 698 62 984 10 718 1551 2024 416 2089 792 1687 1324 1507 309 652 188 513 860 1561 332 1002 346 755 1081 1952 1465 1819 1414 2002 59 2163 276 935 735 819 168 2106 936 1059 1031 1840 935 1864 132 691 878 1934 181 733 627 2150 1675 1768 240 805 687 1098 806 2024 1170 1757 702 1515 1153 1548 610 813 243 978 254 827 9 2000 325 1204 1616 2091 8 784 318 639 1835 1924 669 1375 712 791 1688 2143 498 1259 1382 1712 155 228 191 1674 854 1415 112 1711 1744 2001 733 2155 346 936 128 1012 582 718 1025 1190 565 730 1130 2096 1702 2116 902 1253 296 917 957 1696 62 1474 1668 2045 946 1940 35 …
Output: NO

Example 2:

Input: 199 3674 50 134 149 180 184 199 52 108 19 180 82 117 41 111 61 63 159 170 42 192 146 185 112 142 5 169 34 35 85 186 76 90 53 79 41 43 20 166 30 76 9 170 75 125 86 91 7 71 129 173 4 65 36 147 123 169 184 190 60 118 7 35 98 103 26 175 48 86 117 139 11 26 11 35 136 188 44 93 43 123 32 98 132 174 158 171 27 80 152 153 68 102 64 126 9 158 47 142 35 135 140 166 63 82 27 109 57 176 101 180 43 120 64 109 7 110 8 119 82 188 79 155 49 53 110 176 53 104 43 164 17 127 36 87 37 73 131 181 7 97 33 144 34 53 82 85 132 152 75 155 110 140 140 182 33 132 169 175 68 167 49 69 88 122 40 82 55 120 52 146 77 149 4 128 62 165 101 164 90 176 65 195 1 8 112 114 5 163 23 138 129 139 155 177 126 188 14 99 76 193 30 100 10 121 78 148 138 163 29 89 124 136 34 145 120 166 50 63 98 102 3 92 192 197 31 106 122 148 103 16…
Output: NO

Example 3:

Input: 1594 1269 38 1564 148 1028 209 848 1345 1461 843 1201 219 317 1125 1315 242 1050 72 1479 922 977 925 1327 36 1580 81 120 958 1476 928 1011 615 703 67 504 250 1507 454 1153 769 1031 89 394 66 1567 259 574 481 1402 1058 1442 458 1166 601 1201 161 1440 927 1138 217 1543 1174 1573 138 698 237 724 111 396 436 1424 120 1580 1217 1565 774 1021 893 1160 171 804 290 427 368 521 477 581 83 987 773 871 515 1344 588 1576 123 1512 407 432 212 1085 346 1123 434 1441 237 342 1176 1376 41 212 142 515 139 380 600 1108 590 715 472 792 517 1274 237 857 814 1165 560 971 694 1248 1009 1210 115 1399 145 658 489 883 914 1223 251 1282 849 1244 1269 1572 99 469 780 1419 9 864 18 699 617 758 436 696 1127 1240 40 1573 826 1334 239 1003 860 1026 1005 1590 450 619 387 1340 644 1189 844 1583 1305 1566 864 1584 605 1145…
Output: NO

Constraints:

1 <= n <= 2301; 0 <= m <= 4602; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
The tunnels Two Guilds Puzzle - MEDIUM Coding Problem | CodeTikki