CT62421

Brass bridges Two Guilds

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The quartermaster Nils has been asked to secure the caravan contract. On the desk lies a long table of bridges readings. 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 <= 1316; 0 <= m <= 2632; self-edges make the answer NO.

Example 1:

Input: 567 1835 1 2 2 3 1 3 37 471 176 559 233 447 392 563 68 528 22 335 35 153 21 179 106 169 198 305 115 561 167 223 472 528 266 491 77 334 249 390 139 280 109 374 170 516 89 205 208 219 3 372 78 369 182 277 116 186 163 328 30 265 45 267 168 557 44 145 315 407 41 396 52 469 154 472 164 472 107 225 285 393 192 437 153 481 335 458 213 505 149 227 84 221 444 552 48 350 34 300 368 428 43 362 78 271 126 322 241 468 123 530 67 509 353 553 4 303 268 535 45 464 154 285 51 87 239 363 544 553 58 304 171 311 155 277 460 473 326 554 370 399 415 449 498 519 149 377 15 217 36 416 192 515 363 367 103 420 16 49 456 479 50 335 278 542 131 414 167 450 248 512 13 295 230 425 301 392 306 377 81 253 34 517 134 334 409 411 277 362 100 112 75 553 220 236 414 495 383 449 481 537 168 324 187 266 100 428 197 372 80 223 …
Output: NO

Example 2:

Input: 666 1129 1 2 2 3 1 3 259 296 152 650 51 368 197 361 234 519 498 499 4 298 72 262 438 662 104 521 367 407 48 101 104 409 327 430 42 506 98 187 245 468 84 126 293 657 446 563 328 548 393 459 134 628 396 666 172 616 366 464 148 220 24 575 195 228 6 277 332 407 188 545 252 534 223 342 151 628 67 332 63 582 27 652 45 511 41 221 167 469 351 634 124 431 53 173 605 611 181 635 484 595 216 310 32 249 389 449 208 277 89 442 483 488 129 423 51 57 280 566 180 474 599 627 26 88 321 592 39 167 141 522 180 541 76 528 55 88 218 588 82 317 153 300 205 293 99 387 542 583 524 525 436 567 112 331 89 194 46 289 263 602 252 337 490 652 455 641 89 468 154 278 21 285 176 569 6 521 159 625 201 413 487 503 247 355 75 547 99 624 164 276 30 345 296 398 137 188 353 382 111 417 364 657 490 655 197 289 253 565 250 517 4…
Output: NO

Example 3:

Input: 985 107 846 915 527 729 96 359 666 785 765 806 300 488 200 756 609 625 457 728 236 538 62 672 232 449 294 951 363 875 321 777 86 588 729 953 85 170 235 452 72 811 684 899 65 280 353 569 514 763 198 488 609 957 688 968 703 875 120 946 440 779 296 950 120 400 697 731 23 509 300 664 645 808 104 180 332 335 323 629 385 804 501 769 506 675 23 783 154 472 601 895 599 865 894 929 267 576 588 959 105 527 334 538 143 183 503 804 182 808 53 193 100 505 222 764 602 811 125 282 168 942 105 116 574 649 70 740 334 387 132 624 193 903 428 720 55 469 649 847 332 447 173 325 73 734 412 541 488 962 376 980 540 935 9 833 585 886 934 978 382 727 193 262 354 563 294 458 233 465 603 634 386 879 421 617 744 748 437 548 339 401 519 905 233 894 146 935 289 881 27 851 118 815 114 583 723 768 402 555 27 788 41 126 8…
Output: YES

Constraints:

1 <= n <= 1316; 0 <= m <= 2632; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Brass bridges Two Guilds - MEDIUM Coding Problem | CodeTikki