CT61640

The Two Guilds of the Saffron bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the saffron fields of Marigold Row, Envoy studies rows of bridges entries. One clean number will settle the guild's oldest argument. 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 <= 1571; 0 <= m <= 3142; self-edges make the answer NO.

Example 1:

Input: 925 1225 762 796 111 705 52 350 134 837 363 608 234 419 30 218 660 837 714 847 128 432 436 805 607 905 89 737 563 655 285 447 439 704 6 760 465 776 177 465 689 713 622 684 201 870 772 844 51 477 252 913 294 470 4 785 152 570 284 342 111 405 242 671 318 716 332 355 372 599 369 723 18 787 59 683 182 536 260 684 469 477 211 297 235 673 296 385 672 849 494 873 420 544 143 801 518 653 670 885 51 612 784 857 18 33 387 896 445 606 277 781 227 371 514 874 294 775 756 920 452 658 443 448 74 709 646 783 43 129 90 237 592 682 423 922 37 486 721 792 700 742 433 455 102 414 51 253 407 796 135 371 234 812 72 752 173 528 227 439 452 924 343 745 300 373 2 531 536 715 355 674 72 582 235 871 111 198 242 796 30 320 215 579 659 872 815 865 527 672 114 652 100 155 233 730 122 668 20 652 240 472 296 453 835 878…
Output: NO

Example 2:

Input: 833 697 379 801 464 567 762 789 276 563 310 607 437 464 475 527 399 491 160 693 308 463 271 774 230 603 69 404 272 774 3 91 726 759 272 594 655 808 241 308 130 161 53 423 13 600 214 650 170 310 214 486 278 733 279 316 202 373 96 303 155 554 168 471 85 129 86 597 273 505 306 339 115 767 252 524 555 691 418 456 281 455 16 480 651 805 324 797 259 792 218 526 630 765 67 505 89 636 234 647 176 361 181 242 400 614 357 434 285 402 97 808 179 402 347 522 137 375 196 246 238 484 377 572 157 404 274 376 543 603 86 240 372 420 530 637 583 781 110 516 522 659 295 788 619 693 92 244 168 763 390 651 14 459 630 764 109 660 489 617 45 456 515 801 495 615 801 831 440 454 76 532 77 497 469 652 510 620 43 706 242 823 409 450 164 443 25 680 278 631 510 830 313 566 435 507 154 287 93 252 160 251 225 255 333 46…
Output: NO

Example 3:

Input: 323 671 41 118 50 244 28 256 99 242 18 71 3 75 30 292 261 307 177 257 7 77 57 91 144 231 28 230 100 133 31 59 202 315 124 228 74 212 244 280 15 172 156 180 15 263 233 271 103 296 247 284 3 79 120 157 111 135 209 265 182 287 60 117 83 179 55 256 256 259 40 300 74 104 170 271 191 224 18 227 81 164 159 271 35 199 22 249 296 305 135 147 14 321 37 201 73 194 25 86 3 25 169 182 179 254 144 320 271 314 89 135 47 162 115 224 49 165 211 245 32 178 145 305 5 77 174 318 203 288 99 269 168 182 199 236 9 25 104 217 96 264 169 322 53 305 83 107 79 314 50 115 138 237 25 40 12 95 187 299 194 211 75 138 56 69 108 167 107 247 99 320 146 247 21 24 56 212 133 320 45 235 123 195 255 286 79 323 99 218 185 201 64 200 12 137 154 282 172 209 38 54 68 171 21 75 188 221 29 44 191 313 209 322 247 304 131 136 63 93 84…
Output: NO

Constraints:

1 <= n <= 1571; 0 <= m <= 3142; self-edges make the answer NO.

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