CT59052

Last tunnels of Shepherd

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the moonlit lagoon of Selene as Shepherd unrolls the day's manifest of tunnels. The tally will decide the next shipment. 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 <= 1930; 0 <= m <= 3860; self-edges make the answer NO.

Example 1:

Input: 1838 3132 1486 1577 357 980 675 1347 134 1285 644 715 81 642 1095 1178 1335 1591 965 1130 572 1785 1412 1608 623 1743 838 1012 879 1014 465 1445 823 1751 916 1582 1251 1265 866 1655 1029 1281 1145 1505 384 649 422 1298 366 1724 488 1007 1181 1335 480 1054 566 1579 615 1825 556 1100 781 1199 67 172 592 1745 1708 1743 430 588 508 1290 41 1226 263 1532 1057 1265 753 1090 220 914 1267 1323 415 1639 905 933 633 1527 382 1130 201 1540 138 453 188 991 610 1589 53 442 607 1317 779 1088 1181 1459 219 1800 142 900 604 1656 878 1554 581 1097 939 1730 1524 1530 964 1057 166 1556 1170 1491 6 903 683 1740 283 1826 112 247 64 157 731 1610 54 1203 570 1693 378 408 364 1485 469 1836 1344 1774 898 1625 1219 1701 726 1532 379 1490 453 678 1305 1548 1730 1765 1172 1832 702 733 238 1563 523 968 1180 1274 1077 …
Output: NO

Example 2:

Input: 536 240 58 166 322 337 153 492 311 425 326 363 349 491 155 424 84 434 233 366 81 364 339 407 93 287 364 427 15 213 90 251 128 238 428 455 111 309 331 350 249 359 150 398 62 167 142 151 109 304 98 396 72 479 79 94 60 220 190 210 307 536 30 332 73 142 229 302 254 293 22 245 218 296 19 289 362 445 95 450 124 207 113 141 266 517 451 488 6 263 146 223 174 535 507 509 40 112 58 96 23 493 139 364 47 289 207 422 288 340 302 336 252 356 263 436 20 196 340 502 328 383 303 411 334 428 454 471 156 337 157 164 54 185 134 368 212 290 406 449 336 472 296 440 373 501 331 357 315 508 244 347 43 415 120 500 50 364 224 394 125 175 75 131 430 506 237 445 238 425 254 426 148 465 247 317 356 424 87 137 294 513 254 259 84 265 234 300 484 526 323 492 146 201 201 202 179 420 153 419 287 456 60 409 104 466 459 522 …
Output: YES

Example 3:

Input: 377 333 1 2 2 3 1 3 51 187 71 362 79 141 127 351 83 328 42 362 134 345 185 353 301 330 232 234 112 266 91 223 31 93 277 370 92 181 297 373 52 199 6 217 40 376 206 275 66 77 284 366 132 325 121 261 115 188 178 254 57 95 55 65 37 333 34 243 47 236 13 253 127 133 42 340 293 366 117 202 137 194 37 348 181 209 10 369 168 357 245 274 133 299 137 274 65 242 143 237 235 290 22 157 245 278 196 270 64 238 311 324 141 168 146 230 294 340 75 310 69 152 261 367 254 271 33 239 2 315 321 341 100 213 105 229 30 160 105 146 184 283 215 318 238 345 42 111 54 313 14 24 37 149 173 372 92 266 103 224 118 292 134 308 12 204 7 25 234 377 33 190 320 337 21 95 277 342 299 345 72 96 106 170 153 172 178 266 175 329 53 372 104 188 128 221 231 248 118 296 47 82 71 248 229 341 257 349 203 291 36 155 199 244 77 189 73 3…
Output: NO

Constraints:

1 <= n <= 1930; 0 <= m <= 3860; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Last tunnels of Shepherd - MEDIUM Coding Problem | CodeTikki