CT60216

The corridors at Longlegs

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the heron rookery of Longlegs opens only for a perfect tally of corridors. Dante means to find out. 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 <= 2844; 0 <= m <= 5688; self-edges make the answer NO.

Example 1:

Input: 512 1892 296 467 260 392 93 419 31 166 151 335 297 401 329 510 74 164 411 416 320 419 244 447 88 301 27 363 140 344 4 197 42 206 3 47 208 480 122 281 156 455 384 424 49 455 169 446 340 446 228 434 387 496 437 464 235 306 415 491 15 246 391 500 82 176 90 395 196 284 107 156 227 243 203 270 194 509 335 370 47 311 210 431 129 385 76 289 124 297 217 412 329 331 89 98 40 157 269 337 175 391 402 511 273 483 93 98 84 244 285 466 76 152 2 504 294 443 209 232 11 317 46 103 70 468 118 393 55 130 188 467 184 349 47 292 336 345 46 357 125 397 304 486 200 410 209 449 311 472 246 284 158 359 33 161 103 404 57 240 116 325 13 494 187 431 196 233 240 379 89 252 218 483 148 188 197 199 191 326 62 223 168 475 386 471 134 187 73 395 13 459 231 345 8 25 73 180 23 262 136 231 299 462 23 217 295 494 13 512 481 4…
Output: NO

Example 2:

Input: 1247 1786 711 913 326 681 494 745 260 954 295 1017 186 516 495 1191 272 1198 105 495 2 305 47 1038 365 369 140 277 746 989 263 1245 1031 1220 294 395 73 601 143 321 352 1102 819 1072 397 1020 750 1185 425 987 622 1124 297 1126 552 1180 108 905 917 1237 366 1048 757 1243 297 491 461 644 495 998 114 314 607 967 111 453 153 500 416 472 125 346 640 1112 51 759 514 972 201 982 675 998 146 727 67 489 357 1244 307 739 146 1213 1017 1113 376 692 968 1077 215 519 84 599 498 793 209 645 808 929 88 188 855 1204 451 901 35 811 1075 1171 134 739 1177 1235 806 1012 20 720 1001 1111 326 579 331 710 1071 1193 860 970 921 1239 415 554 56 648 372 552 308 908 189 1122 272 808 3 1016 33 846 188 194 93 827 604 1125 124 165 141 229 298 481 59 246 47 718 676 1027 446 468 163 844 237 383 208 599 802 1055 237 517 …
Output: NO

Example 3:

Input: 2563 4142 1 2 2 3 1 3 2445 2457 1647 2402 477 708 743 1731 158 1452 374 744 488 527 243 1691 78 2384 618 2547 290 964 776 1368 512 1462 1975 2041 1617 1636 1196 1977 2270 2396 898 1347 1451 2334 639 1239 1097 2286 2379 2446 1305 1950 1064 2475 1043 1533 549 1876 463 868 614 2189 1441 1950 602 2232 116 2325 360 1988 719 2083 939 1748 487 1004 2011 2074 432 2392 1433 2197 10 1057 860 1852 328 407 796 1276 1726 2056 1502 1746 520 1010 2318 2338 1349 1984 2076 2438 743 2115 772 1803 1230 2538 1744 1980 757 1015 75 1824 1302 2082 286 1462 43 1659 2227 2255 1220 1484 309 2163 1442 2009 1847 2328 511 783 2256 2439 208 1021 926 1362 791 1279 499 1531 396 731 1087 1986 276 2388 920 1745 376 562 1043 2004 241 2078 86 2444 1143 1540 1903 2323 639 1008 855 1164 960 1091 102 2079 535 2387 1383 1807 181…
Output: NO

Constraints:

1 <= n <= 2844; 0 <= m <= 5688; self-edges make the answer NO.

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