CT60556

Mira's roads Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Mira found an old ledger of roads in the stall attic at the glass towers of Prismhaven. 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 <= 2310; 0 <= m <= 4620; self-edges make the answer NO.

Example 1:

Input: 1031 406 32 523 366 612 291 452 109 457 291 732 203 509 526 794 677 848 165 552 44 844 624 1011 437 834 630 967 216 1027 713 730 367 471 198 996 115 769 323 414 200 204 487 786 367 463 209 788 144 313 188 909 200 1016 410 802 364 385 261 678 721 758 8 191 2 456 273 965 410 539 261 408 200 771 115 128 363 873 648 852 148 272 315 508 470 668 102 496 389 997 53 686 587 588 246 871 964 982 4 672 434 559 166 1024 222 641 668 772 314 440 177 634 427 957 303 950 61 894 165 709 342 706 216 999 172 780 81 763 265 835 744 908 389 585 889 981 211 530 961 971 3 620 341 448 972 1007 252 944 845 960 323 800 7 428 446 909 128 388 277 353 66 1006 378 894 547 1025 353 591 578 731 339 739 88 1029 174 409 249 825 342 695 351 534 205 809 44 384 48 901 651 892 456 578 94 216 52 764 316 780 3 332 332 362 51 324…
Output: YES

Example 2:

Input: 445 2047 352 435 223 340 35 222 36 231 16 359 173 192 197 304 217 262 231 335 50 74 143 253 135 421 196 363 187 432 270 350 108 410 293 358 8 357 155 331 224 375 80 312 54 121 379 390 28 92 130 341 233 389 209 378 123 353 7 96 153 179 41 65 258 271 7 42 45 88 127 395 329 412 106 299 119 426 120 180 86 229 8 223 114 150 225 407 252 366 79 211 52 223 36 315 33 404 175 254 150 283 142 338 53 175 32 267 325 444 87 418 258 326 71 328 67 303 305 444 347 411 338 433 105 411 78 165 342 445 397 417 63 344 76 418 126 329 15 190 246 444 194 304 24 323 274 305 189 435 94 125 123 444 72 191 144 287 147 183 31 69 14 182 51 439 145 334 306 333 115 259 238 356 145 220 257 388 11 78 421 432 143 333 101 117 139 298 1 127 94 184 62 266 169 199 267 361 213 241 47 60 73 381 220 333 181 242 6 404 200 269 172 38…
Output: NO

Example 3:

Input: 104 539 1 2 2 3 1 3 20 40 91 93 32 35 13 67 32 86 80 100 54 73 58 66 17 30 31 89 28 59 27 86 15 66 73 84 22 46 6 8 45 83 6 20 52 58 33 62 80 94 67 68 40 98 10 86 2 26 22 60 7 70 54 85 1 80 32 95 86 102 38 76 5 52 45 91 26 63 34 38 82 87 40 82 9 78 80 83 28 72 35 45 72 83 60 75 43 49 37 49 40 66 13 51 80 97 70 78 5 30 46 86 6 15 68 77 27 45 68 79 24 31 34 77 25 51 44 59 22 31 32 80 50 58 2 70 23 48 26 93 62 75 51 88 21 24 35 84 12 42 62 91 40 52 41 60 1 6 25 55 53 96 5 61 27 79 44 77 28 38 34 46 16 33 26 42 16 32 76 96 42 64 58 86 5 13 3 34 16 100 50 90 32 93 67 98 16 72 50 67 52 54 4 37 6 25 52 84 18 62 3 100 71 81 56 68 29 94 43 71 5 22 35 50 3 88 45 82 46 62 14 24 76 91 9 30 94 98 31 53 19 77 24 43 46 104 15 91 45 68 29 68 24 61 14 58 5 41 46 64 7 104 30 104 2 81 5 88 14 51 31 36 5 16 11…
Output: NO

Constraints:

1 <= n <= 2310; 0 <= m <= 4620; self-edges make the answer NO.

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