CT48930

Innkeeper and the Two Guilds

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Innkeeper found an old ledger of bridges in the cellar attic at the thorn maze of Bramblecourt. The margin notes pose a precise question. 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 <= 1023; 0 <= m <= 2046; self-edges make the answer NO.

Example 1:

Input: 193 663 1 2 2 3 1 3 62 116 96 153 46 115 127 159 8 118 117 184 12 48 126 182 83 129 139 165 58 87 99 140 82 166 26 114 59 97 34 46 2 161 32 120 82 137 33 89 68 181 21 165 14 139 13 119 47 176 28 156 126 162 64 175 20 41 14 169 80 152 91 107 155 187 108 114 28 30 20 191 151 170 53 90 45 159 122 174 30 150 85 153 93 108 74 151 53 122 46 69 30 134 26 86 23 61 89 93 59 182 3 36 49 167 26 171 51 190 10 93 10 182 150 178 16 86 48 132 3 127 101 132 88 113 30 181 141 156 24 143 23 80 9 135 28 191 37 96 101 104 158 187 34 66 77 111 108 138 44 130 101 162 58 127 114 176 145 168 61 176 84 166 25 93 48 69 98 167 121 177 55 169 7 46 86 126 20 47 9 24 34 79 93 191 8 103 95 122 102 107 106 150 79 103 27 66 171 178 36 161 46 154 49 183 9 158 75 169 64 81 21 154 19 46 37 126 75 152 84 114 97 109 27 126 140…
Output: NO

Example 2:

Input: 519 555 1 2 2 3 1 3 155 386 163 279 135 187 152 347 299 359 330 495 238 515 173 484 353 369 39 177 143 277 121 284 234 237 167 180 330 477 149 378 16 515 65 113 346 351 455 456 330 434 134 216 244 420 278 399 399 432 58 333 130 240 133 350 101 204 80 481 189 289 72 96 303 370 479 497 232 490 417 476 121 459 82 167 347 385 32 203 361 385 5 31 401 474 166 240 27 514 403 488 161 490 346 519 253 486 123 488 72 378 75 117 163 241 212 377 372 509 75 377 349 510 355 400 403 440 194 484 124 257 196 403 9 342 72 302 276 374 17 106 202 286 112 256 80 173 20 69 52 519 134 490 261 383 266 314 158 297 420 459 193 389 198 363 22 294 6 93 74 456 81 83 238 369 270 369 113 293 357 401 114 248 178 310 221 345 25 182 124 251 436 503 221 366 301 411 60 456 64 498 146 205 357 421 33 451 7 266 391 399 277 423 4…
Output: NO

Example 3:

Input: 694 1446 349 668 185 657 398 522 241 543 39 263 350 665 49 614 57 365 404 574 201 630 408 637 574 614 309 442 406 508 47 86 76 681 20 638 213 514 418 642 459 533 18 504 40 222 251 606 277 598 501 578 573 622 186 395 321 397 576 673 524 653 411 606 506 567 6 426 319 416 455 475 110 327 512 658 77 506 271 616 2 601 303 500 97 256 15 421 482 534 135 198 265 554 419 520 325 480 360 656 11 102 86 429 454 635 79 512 430 519 347 428 330 524 465 478 198 678 68 431 352 502 34 626 437 684 122 242 175 683 226 311 352 445 406 469 296 516 125 493 250 258 76 273 12 673 322 686 263 510 189 483 294 602 260 525 476 528 66 249 273 315 610 642 296 551 56 150 585 676 267 477 79 323 196 524 592 638 168 573 80 95 635 653 69 604 122 555 436 495 166 571 179 350 22 395 48 374 82 365 266 270 305 401 283 665 484 519…
Output: NO

Constraints:

1 <= n <= 1023; 0 <= m <= 2046; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Innkeeper and the Two Guilds - MEDIUM Coding Problem | CodeTikki