CT61307

Kian Counts the bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the lakeside town of Mirrormere as Kian unrolls the day's manifest of bridges. 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 <= 1688; 0 <= m <= 3376; self-edges make the answer NO.

Example 1:

Input: 979 1639 433 971 451 452 493 670 381 740 441 676 219 613 73 138 151 263 39 357 412 486 353 728 88 672 253 308 395 489 131 646 267 384 202 791 345 667 584 683 238 764 653 657 399 713 166 915 439 606 233 423 636 916 757 789 264 330 99 591 130 855 292 344 767 958 223 751 222 225 95 831 48 614 216 239 72 414 934 941 296 810 515 558 304 627 204 638 384 729 579 953 65 694 82 886 464 483 710 884 623 703 818 840 63 966 37 308 636 650 384 670 315 894 158 384 435 712 443 960 151 497 303 974 327 623 1 739 253 573 534 962 391 624 69 222 297 776 114 809 400 901 519 633 430 813 235 636 148 658 789 877 505 541 306 391 334 892 594 638 128 292 241 256 84 116 553 674 147 490 293 685 523 734 408 729 651 664 464 917 229 886 152 397 331 951 532 717 269 297 488 593 336 619 51 762 3 871 451 608 390 842 182 729 1…
Output: NO

Example 2:

Input: 836 2 1 2 2 3
Output: YES

Example 3:

Input: 524 1317 1 2 2 3 1 3 140 508 21 131 261 424 233 483 261 320 67 395 141 384 254 438 308 332 24 484 217 491 3 8 23 346 89 94 10 389 175 430 110 492 261 341 112 467 123 328 379 429 273 383 161 344 50 260 343 509 32 459 102 350 197 474 96 264 230 373 86 207 117 489 184 208 85 192 129 229 259 375 34 108 210 262 304 389 355 447 140 441 71 356 190 384 132 352 45 260 329 492 143 144 65 494 166 463 117 462 346 523 90 520 289 382 177 348 156 469 53 63 62 104 482 502 238 302 257 335 390 393 51 244 172 330 296 328 177 305 274 301 378 380 290 518 173 401 50 433 242 330 3 28 278 345 321 517 191 241 79 174 177 237 255 350 160 349 423 475 6 430 85 516 212 503 360 488 103 195 3 324 25 522 152 172 17 62 232 478 28 308 288 333 184 270 185 424 86 242 233 325 169 188 295 345 233 415 173 336 306 370 92 428 286 …
Output: NO

Constraints:

1 <= n <= 1688; 0 <= m <= 3376; self-edges make the answer NO.

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