CT62135

Eklavya and the Northern roads

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Eklavya runs the bakery at the mushroom groves of Fungaldeep. Today the books show a list of roads, 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 <= 2311; 0 <= m <= 4622; self-edges make the answer NO.

Example 1:

Input: 1271 3442 371 1100 686 1047 630 943 288 504 189 280 601 803 124 402 425 1085 528 1220 836 1037 595 1185 369 1253 1120 1215 411 833 99 562 255 309 70 709 124 1188 3 842 110 300 63 642 130 308 148 1175 360 1221 297 1125 79 869 793 1104 10 1140 432 884 994 1108 363 848 603 696 54 1174 646 1125 876 888 180 1183 764 976 633 1047 2 1131 750 846 224 653 249 343 21 112 342 827 597 1001 781 1096 837 1227 677 748 298 558 246 1030 533 1105 43 112 1215 1223 220 727 517 927 311 833 887 1000 108 331 339 445 964 1117 177 587 240 966 64 976 207 430 398 1121 23 638 25 889 186 220 838 1235 54 661 160 983 841 1050 132 419 162 1079 54 1138 102 407 86 291 1131 1255 419 1024 999 1074 522 695 925 1177 248 472 7 78 617 715 890 1027 697 1081 563 1265 103 801 838 884 754 871 796 965 191 929 195 1264 291 623 1023 10…
Output: NO

Example 2:

Input: 659 1001 21 402 132 616 337 398 129 243 244 484 183 199 215 537 277 378 173 247 185 354 379 402 588 632 290 436 352 442 160 365 540 625 244 365 130 390 68 518 117 407 450 558 199 576 339 636 252 470 342 606 117 251 155 354 142 383 428 631 110 428 225 542 519 605 41 541 70 387 624 655 312 436 88 287 419 540 588 601 207 525 77 601 127 654 90 177 119 217 139 322 188 398 13 206 27 127 187 481 221 231 149 187 131 321 422 631 600 603 128 293 220 383 35 238 175 356 74 135 142 589 151 622 561 610 312 361 222 544 194 563 128 302 528 554 97 108 79 388 116 618 189 265 328 653 130 647 206 506 463 611 318 503 160 264 329 571 279 506 179 429 293 432 229 523 180 294 296 587 202 213 260 381 371 528 14 263 34 116 440 456 234 317 42 55 362 447 353 455 539 564 89 211 133 385 569 653 29 539 25 115 225 418 14 …
Output: NO

Example 3:

Input: 2298 1631 1 2 2 3 1 3 676 2108 438 732 857 2259 712 2248 780 1899 471 1445 2182 2185 84 1804 687 1497 663 1479 1001 1973 1193 1843 352 1888 53 1715 505 1307 348 2256 524 714 35 1111 1272 1286 883 1536 217 1829 1751 2036 822 1251 44 2139 350 1184 715 1356 1112 1397 376 2121 215 1729 414 687 571 925 1840 2050 17 530 492 1618 361 1668 1823 2056 95 1700 770 1954 1527 2139 190 664 1620 2004 1804 1856 535 2285 794 2102 83 542 163 2023 963 2151 810 1382 535 811 767 1174 1062 1163 571 1299 843 1686 1782 1827 1239 1766 461 2040 63 1229 424 1772 317 339 1436 1607 229 1925 526 1825 243 1719 2147 2167 1674 1964 529 801 1961 2185 1045 1260 829 2132 1234 1252 991 1626 572 1631 1343 1467 660 1687 819 2028 1008 2066 180 1122 782 1433 1671 2257 382 1404 109 2189 1573 2042 766 1927 560 595 656 1776 62 128 4…
Output: NO

Constraints:

1 <= n <= 2311; 0 <= m <= 4622; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Eklavya and the Northern roads - MEDIUM Coding Problem | CodeTikki