CT47663

The bridges Two Guilds Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Petr found an old ledger of bridges in the bakery attic at the granite steps of Stonehallow. 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 <= 1790; 0 <= m <= 3580; self-edges make the answer NO.

Example 1:

Input: 113 307 1 2 2 3 1 3 36 90 15 31 79 94 4 65 67 75 9 48 64 70 35 80 15 45 31 38 33 89 61 96 49 105 25 57 9 101 78 88 9 52 23 62 92 100 52 64 65 98 48 105 36 70 27 96 59 75 65 84 74 83 13 48 110 112 51 72 2 9 2 68 88 93 2 52 55 106 3 31 29 43 35 49 60 109 64 105 67 90 42 98 33 56 23 68 2 66 26 89 80 94 49 85 53 102 33 53 28 60 91 96 80 112 23 73 94 112 61 78 50 53 55 91 13 19 28 91 20 32 20 50 34 112 68 79 37 52 81 82 52 65 11 88 20 43 13 71 65 104 97 108 11 17 18 92 83 95 79 85 2 112 29 112 67 96 8 92 28 84 74 105 27 76 100 101 26 33 69 96 29 83 47 54 46 100 60 80 78 99 42 103 31 52 86 93 19 56 37 49 40 113 46 66 19 107 65 76 40 100 62 97 25 62 17 59 42 89 72 109 16 112 4 90 85 110 31 49 3 101 62 82 31 60 76 77 30 36 45 104 40 90 49 81 16 19 24 50 77 97 30 81 1 86 19 49 15 74 46 49 11 57 56 …
Output: NO

Example 2:

Input: 625 1212 88 261 176 345 285 461 337 376 4 102 15 610 210 285 380 528 42 247 429 546 14 394 271 460 247 574 185 335 5 47 180 486 51 494 414 589 440 482 388 425 120 623 85 311 299 477 190 481 120 472 46 218 55 213 457 538 177 220 544 595 27 455 240 412 163 590 419 625 76 189 175 567 206 435 22 337 68 164 511 588 221 536 67 293 129 354 96 439 24 28 162 202 123 188 155 332 187 490 425 457 247 546 208 247 61 431 165 215 321 518 96 225 159 323 71 515 5 494 74 567 21 327 144 304 34 360 247 466 528 529 499 597 512 619 21 586 136 600 169 244 24 613 377 471 349 380 331 446 150 277 105 256 378 562 22 273 75 424 8 156 248 313 130 304 79 613 123 365 1 100 322 531 275 493 23 412 14 152 251 504 110 261 277 287 460 567 266 369 176 570 314 565 37 85 122 603 483 612 118 256 121 389 16 129 359 535 60 579 503…
Output: NO

Example 3:

Input: 1039 429 1 2 2 3 1 3 343 868 624 710 471 990 493 968 389 847 373 564 68 213 161 230 469 754 126 860 176 489 63 1015 273 663 1 461 217 708 448 663 116 198 237 252 198 344 632 1017 505 844 233 843 673 827 375 673 140 487 91 413 433 1013 250 931 202 733 226 429 744 1032 663 952 505 814 95 398 392 729 22 618 516 997 266 711 776 1006 257 281 462 618 936 951 962 970 184 277 680 886 565 1020 224 638 85 241 601 941 91 127 521 773 838 948 92 171 678 990 31 121 318 713 536 726 248 798 610 640 342 912 331 366 347 477 78 376 391 949 53 696 509 800 136 744 609 961 367 505 170 550 201 229 159 861 118 928 676 886 768 906 897 1001 141 914 379 940 73 987 422 982 182 389 688 810 840 935 148 868 43 603 352 631 527 685 331 1016 346 415 489 617 54 395 206 310 247 755 245 742 318 341 120 904 523 685 60 112 228 …
Output: NO

Constraints:

1 <= n <= 1790; 0 <= m <= 3580; self-edges make the answer NO.

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