CT37433

Lata's bridges Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Lata found an old ledger of bridges in the shed attic at the crane marshes of Stillwater. 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 <= 3079; 0 <= m <= 6158; self-edges make the answer NO.

Example 1:

Input: 529 2938 414 459 55 394 57 70 84 403 65 510 322 529 315 355 238 442 61 305 298 356 60 164 42 98 302 387 259 509 308 412 11 406 42 86 102 243 195 338 12 377 287 463 397 469 250 323 341 454 15 496 152 467 2 504 380 528 136 389 3 67 4 349 330 341 287 521 219 498 378 473 117 275 194 510 332 457 132 409 180 197 106 143 330 490 434 516 451 529 468 483 159 479 3 317 248 337 48 250 31 370 353 387 110 130 207 483 161 175 364 513 156 473 124 216 8 327 54 368 103 415 16 216 245 405 273 426 205 482 75 172 251 262 206 371 68 385 152 382 187 337 325 363 175 182 149 340 262 424 279 344 77 476 40 180 249 320 415 520 207 377 436 448 59 525 21 512 140 426 114 344 66 180 128 382 374 512 157 198 7 485 41 59 9 524 229 480 90 95 341 432 108 436 259 389 174 444 110 440 41 337 249 394 211 287 300 478 376 487 54 1…
Output: NO

Example 2:

Input: 689 5530 451 575 166 187 626 648 70 319 404 639 129 209 320 530 69 292 560 613 125 502 634 649 404 521 22 158 33 350 333 569 345 531 332 471 210 356 395 656 12 375 471 476 40 544 198 424 240 680 202 560 398 656 83 221 455 666 167 256 249 543 210 406 228 327 131 495 445 617 340 659 89 515 300 321 62 259 350 459 272 581 196 256 347 379 112 236 31 72 555 566 295 673 311 421 206 487 368 441 400 633 379 457 29 517 197 320 504 680 472 577 402 625 180 338 358 612 322 492 5 637 120 427 150 424 328 647 124 659 373 467 512 676 17 470 404 415 371 408 516 687 323 402 27 278 290 311 154 537 318 403 162 459 84 468 93 240 263 607 298 348 187 548 165 195 468 526 116 520 128 556 102 199 180 420 75 204 106 178 15 678 143 684 117 433 226 297 164 566 221 511 96 561 360 505 33 211 386 527 676 681 370 624 5 64 …
Output: NO

Example 3:

Input: 126 3504 90 118 52 106 84 125 53 107 16 83 67 81 116 122 57 96 24 37 48 107 11 59 97 107 100 103 51 66 46 83 22 50 89 123 97 109 101 102 26 94 18 118 39 112 3 97 36 62 27 90 47 84 27 115 34 103 47 62 5 16 50 80 33 85 50 56 17 93 77 122 11 103 68 117 56 125 64 65 77 91 103 123 48 69 82 110 5 48 36 97 91 116 35 72 4 31 41 101 23 81 23 46 48 84 33 47 72 113 1 17 30 105 60 98 14 74 26 71 15 115 16 61 73 113 96 124 28 76 51 109 24 41 77 115 37 86 17 25 47 75 16 41 105 107 91 92 47 57 36 50 64 75 50 74 22 74 27 95 65 69 112 126 3 10 58 73 110 120 106 113 7 17 22 36 76 101 98 108 29 90 17 55 100 123 10 23 85 125 26 62 56 105 21 117 12 28 54 81 54 55 17 56 72 103 37 92 49 121 64 116 33 66 28 118 49 68 31 55 26 32 41 102 51 64 31 89 41 77 7 120 42 62 39 80 4 109 5 81 57 81 60 94 21 104 48 120 82 12…
Output: NO

Constraints:

1 <= n <= 3079; 0 <= m <= 6158; self-edges make the answer NO.

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