CT37298

The Two Guilds Beneath Nacre Bay

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the pearl fisheries of Nacre Bay, Dante the bookkeeper keeps careful count of the tunnels. Verify the ledger before the auditors arrive, every figure matters. 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 <= 2201; 0 <= m <= 4402; self-edges make the answer NO.

Example 1:

Input: 471 3086 38 147 65 78 297 413 26 229 72 146 105 432 240 344 49 440 318 405 119 170 322 364 263 455 312 400 307 410 57 466 283 385 151 222 5 289 19 404 245 400 38 403 346 450 29 172 167 432 323 454 170 196 404 434 285 324 124 317 132 361 56 206 12 291 132 229 234 451 392 448 152 165 229 466 76 113 4 245 25 406 201 335 93 360 22 83 352 431 273 449 256 391 8 113 109 357 133 352 132 306 132 198 85 409 113 251 26 442 133 164 43 278 145 455 87 357 5 82 122 244 232 379 184 185 420 424 142 415 285 471 22 262 213 450 205 305 46 139 230 380 11 441 210 324 142 275 89 381 224 310 300 439 1 166 24 456 278 439 59 314 22 233 69 353 1 75 364 439 394 435 293 442 332 462 89 271 89 156 63 263 202 246 160 172 304 342 34 296 100 353 82 457 87 321 202 328 86 119 307 310 122 443 315 369 164 251 182 390 91 204 20…
Output: NO

Example 2:

Input: 1860 670 449 1778 1219 1451 39 1315 1083 1627 439 1475 396 1081 744 1138 1057 1360 1661 1837 1408 1554 801 811 19 1007 680 1449 454 1365 1575 1833 1086 1401 378 958 1604 1706 253 1083 374 993 70 1584 127 1016 145 182 358 1518 970 1286 1354 1844 421 902 108 895 491 923 516 1602 51 1357 371 1816 1003 1239 362 643 38 1466 300 1422 923 1440 271 1618 22 1342 543 1280 1602 1632 483 744 323 1392 295 354 298 1343 642 1410 303 1347 440 1158 1200 1703 121 464 277 458 725 1137 301 420 768 1297 281 1396 1006 1691 487 1130 1052 1730 791 1694 1002 1417 758 1598 2 150 77 201 1087 1224 377 1817 531 1173 1295 1685 1799 1832 936 1206 824 1456 1277 1411 1059 1388 302 1206 928 929 27 259 659 791 36 1292 976 1534 129 1141 536 969 692 1483 203 1282 424 1005 1228 1238 223 1592 400 1498 1116 1187 163 705 376 666 …
Output: NO

Example 3:

Input: 277 1717 1 2 2 3 1 3 34 166 67 195 6 238 111 246 4 82 62 134 73 236 21 175 87 179 58 233 118 173 182 256 5 66 2 144 1 178 121 259 112 269 68 122 75 200 112 122 110 181 98 176 9 93 167 172 4 114 236 277 27 143 85 219 197 229 10 56 12 60 21 121 63 226 43 180 71 274 8 229 191 221 51 182 202 230 49 178 11 94 74 161 205 228 180 219 86 246 151 209 170 264 70 191 73 186 185 210 102 211 169 247 66 209 5 117 26 165 54 146 22 249 147 197 106 133 248 259 97 201 55 184 229 242 124 241 192 266 47 151 47 96 197 213 146 244 26 50 231 277 36 61 77 239 40 171 106 205 43 229 111 156 21 47 97 134 65 276 35 65 64 166 61 261 23 28 54 89 81 86 70 180 40 163 72 276 30 214 155 220 49 131 20 156 22 129 135 182 111 267 49 146 196 276 43 243 60 148 53 142 49 171 228 264 114 147 58 256 53 74 143 195 102 261 35 193 34…
Output: NO

Constraints:

1 <= n <= 2201; 0 <= m <= 4402; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
The Two Guilds Beneath Nacre Bay - MEDIUM Coding Problem | CodeTikki