CT36589

The bridges at Bloomhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the tulip beds of Bloomhaven; Sable weighs the day's bridges manifests and starts the calculations. 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 <= 1076; 0 <= m <= 2152; self-edges make the answer NO.

Example 1:

Input: 930 1715 1 2 2 3 1 3 275 377 449 752 607 621 361 665 460 718 348 802 628 839 434 674 712 851 422 525 466 798 632 691 42 88 618 644 295 621 397 593 272 830 91 909 591 681 329 409 208 695 70 724 636 835 219 357 263 394 581 857 133 860 173 725 669 836 288 598 2 302 127 547 307 474 530 884 332 498 17 862 612 864 225 720 404 530 361 538 174 425 105 780 181 257 24 659 224 511 106 459 248 347 491 674 299 594 220 679 168 519 346 711 134 485 278 717 109 251 611 625 533 841 54 643 143 248 173 887 234 246 398 552 147 771 601 638 479 658 62 453 887 904 338 903 57 734 60 299 303 768 478 913 55 225 336 670 98 869 539 549 425 562 198 875 169 534 431 908 1 387 188 652 368 644 286 497 98 357 252 907 122 813 90 266 206 363 50 890 53 297 314 637 478 699 54 608 565 849 596 626 597 918 125 254 588 909 579 724 …
Output: NO

Example 2:

Input: 138 187 46 72 14 125 37 97 31 97 96 110 112 115 78 100 15 33 61 129 12 123 68 113 2 44 52 60 25 36 62 69 45 51 24 57 19 123 110 137 74 116 2 10 26 70 23 112 22 127 111 126 73 75 20 119 102 138 128 132 7 88 53 58 30 113 62 71 51 56 63 114 67 100 19 44 1 38 110 120 69 127 28 104 2 92 50 95 44 133 42 58 12 21 53 88 122 138 94 131 77 107 75 125 24 60 21 37 37 58 105 134 18 91 21 32 100 108 37 74 56 58 96 107 6 124 21 69 37 116 3 134 33 109 57 122 62 87 33 74 62 70 4 30 13 110 35 61 30 42 25 27 55 93 13 47 17 36 42 133 79 131 5 68 15 17 68 82 57 113 10 62 14 77 10 25 32 33 14 45 84 124 33 91 13 90 10 95 30 125 1 138 24 90 81 97 117 127 58 121 30 69 23 51 102 117 18 40 128 129 58 106 78 123 15 127 72 74 107 138 1 35 80 87 22 103 46 133 8 14 12 86 21 93 66 103 106 113 14 38 7 55 76 105 63 97 14 1…
Output: NO

Example 3:

Input: 465 1069 1 2 2 3 1 3 160 368 107 300 54 444 225 282 312 391 272 313 165 351 265 461 88 284 389 406 61 331 375 401 52 311 173 452 174 189 21 112 189 395 201 398 256 320 149 301 390 432 420 456 205 345 142 167 265 323 111 226 74 231 217 414 104 114 350 365 204 448 22 29 404 448 127 313 226 374 221 303 195 226 398 462 70 425 260 435 274 281 167 335 193 201 190 420 323 421 9 303 102 376 33 368 352 460 291 464 170 373 261 301 196 234 297 398 199 331 120 411 132 232 147 329 161 205 380 419 254 435 41 44 14 169 225 269 190 430 33 464 167 301 176 354 338 401 199 457 86 391 68 369 342 364 215 464 275 427 214 419 346 356 266 282 82 109 335 344 447 456 128 274 52 413 288 407 51 96 134 367 269 379 48 299 23 392 145 194 58 64 65 216 306 336 59 357 46 180 276 363 114 137 313 319 269 442 102 381 208 294 …
Output: NO

Constraints:

1 <= n <= 1076; 0 <= m <= 2152; self-edges make the answer NO.

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