CT61029

Boris's Ledger of corridors

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Boris runs the ropewalk at the cotton rows of Whitewick. Today the books show a list of corridors, and the numbers must be worked out before sundown. 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 <= 2109; 0 <= m <= 4218; self-edges make the answer NO.

Example 1:

Input: 417 1316 1 2 2 3 1 3 44 186 83 317 234 372 72 389 220 412 252 290 60 223 130 385 244 263 62 414 203 263 52 405 151 326 154 202 2 181 160 401 6 326 193 351 98 355 6 111 168 301 157 205 48 349 59 338 204 315 140 219 216 295 93 156 211 319 148 370 153 336 245 392 238 343 283 377 2 289 136 318 358 407 130 383 241 261 119 179 3 90 202 407 46 217 22 121 356 374 144 232 206 256 263 392 104 283 100 110 18 312 121 337 323 344 44 70 20 253 132 133 84 397 4 323 114 215 166 190 90 287 13 344 156 277 303 313 120 245 131 292 192 233 373 412 68 377 163 353 245 331 62 415 210 271 136 166 177 236 210 361 122 221 51 100 29 102 6 215 15 301 33 49 167 224 182 315 62 377 352 408 57 227 160 300 44 367 44 228 29 42 125 382 164 378 133 405 101 330 89 321 155 372 157 335 74 383 45 220 5 81 119 256 199 217 189 347 …
Output: NO

Example 2:

Input: 983 680 81 750 24 325 377 874 218 623 112 901 492 576 176 927 2 747 346 579 54 64 426 738 107 741 498 675 909 981 124 239 692 930 226 579 291 666 212 365 183 198 436 590 263 678 751 891 568 613 261 335 317 885 55 197 137 690 121 554 582 670 95 495 187 533 16 133 6 704 218 463 801 955 571 820 591 728 204 354 527 903 213 556 386 497 612 774 377 810 23 816 701 713 924 963 278 356 336 724 556 909 27 336 359 859 202 494 544 909 674 813 182 812 341 946 786 902 63 719 189 535 276 802 690 981 68 823 411 642 114 199 676 785 208 302 450 851 117 386 403 714 151 823 523 968 50 880 39 432 119 152 18 37 376 836 113 143 952 963 181 616 338 422 75 459 622 733 252 483 468 590 220 901 254 800 55 584 586 741 133 580 204 444 723 838 334 533 228 697 243 618 353 680 234 830 323 463 287 385 562 882 246 790 547 7…
Output: NO

Example 3:

Input: 1291 4073 1 2 2 3 1 3 437 1021 205 750 243 1072 579 1067 9 703 153 871 2 243 276 430 96 999 214 930 387 670 219 1057 382 615 596 987 60 162 322 469 109 1035 212 1198 845 927 479 575 281 1216 89 951 212 227 488 721 822 977 297 1025 331 740 18 1220 375 1129 963 1126 419 819 92 539 396 439 384 631 820 1115 681 1036 1139 1154 690 856 11 1221 388 1203 822 1210 226 1273 473 1229 28 501 375 1161 151 1142 393 630 509 607 16 844 296 426 807 1052 435 699 210 905 34 1146 613 1211 570 571 771 1106 1083 1135 442 949 1046 1263 164 433 66 1138 510 667 92 1026 96 655 37 1160 1027 1186 39 479 147 939 1254 1290 366 1218 307 481 525 1051 374 739 946 1077 422 908 37 720 113 520 523 572 38 1087 665 705 850 950 442 1103 724 1269 114 1013 920 1261 185 1086 1173 1181 5 673 357 834 131 438 489 1088 470 918 28 710 …
Output: NO

Constraints:

1 <= n <= 2109; 0 <= m <= 4218; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Boris's Ledger of corridors - MEDIUM Coding Problem | CodeTikki