CT64805

Last roads of Dante

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Dante inherited the chandlery at the island market of Coralcove along with its curious bookkeeping system for roads. Time to make sense of it. 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 <= 2733; 0 <= m <= 5466; self-edges make the answer NO.

Example 1:

Input: 2497 219 1 2 2 3 1 3 193 1147 627 731 1289 1392 916 2225 1496 1766 1187 1589 679 2293 178 1784 1056 1462 1605 1844 717 1495 472 1900 334 1525 312 449 919 1614 484 700 1727 1878 981 1001 936 2401 169 2484 1997 2045 214 1697 895 2432 1925 2200 326 2185 1528 1933 856 902 1643 1653 1368 2113 1033 1357 2065 2202 518 1042 664 1241 405 1359 1153 1973 1357 2288 45 862 15 2014 1268 1989 474 986 816 982 2048 2474 399 2366 343 2266 439 2389 398 947 120 1476 1577 2032 1096 2277 1801 2240 1224 2485 99 1901 1880 2039 236 2102 75 2331 1534 1613 169 1374 1023 1939 1431 1592 127 296 896 2275 175 430 351 726 439 739 1278 2182 610 1521 208 1978 36 509 865 1069 60 338 358 1654 1038 1480 917 2035 342 825 945 1259 152 606 1259 1644 1874 2134 513 1429 598 1216 1559 2220 182 623 1435 1915 1278 2447 865 2101 646 9…
Output: NO

Example 2:

Input: 2522 1797 600 1000 14 1494 793 2436 1891 2489 53 878 968 2416 1460 1791 2074 2256 539 2161 358 1062 723 2098 1483 2087 341 541 1988 2485 700 2294 1489 1509 611 623 205 1227 1700 2059 254 1660 1646 2178 1611 1835 636 2126 1305 2081 481 2123 1411 1749 1620 2130 696 2132 242 1866 190 217 1183 1855 1408 2305 1347 1795 658 2056 811 2021 1783 2373 644 1741 180 520 637 710 1310 2171 1963 2262 402 2231 1490 1755 644 2031 1585 1776 116 2028 1509 1957 713 1528 305 460 64 706 610 2499 266 856 582 721 1691 1734 115 686 2134 2138 482 522 1008 1427 30 815 1650 1825 1611 1986 167 1711 1177 1799 1622 2012 1796 2209 753 849 206 758 834 936 170 2165 976 1483 1987 2326 1020 1443 587 1535 639 2449 749 822 2008 2416 570 2190 754 2151 1340 1489 581 1471 710 883 63 103 2018 2280 43 2185 264 1703 901 1792 1661 21…
Output: NO

Example 3:

Input: 234 832 93 105 46 71 15 147 139 148 58 232 76 169 71 144 125 157 28 207 2 40 28 49 89 195 140 185 23 216 95 184 27 55 43 196 31 109 111 178 42 141 9 197 96 100 65 234 31 140 71 229 55 127 15 170 123 197 131 212 4 14 31 206 110 122 10 217 40 124 108 169 56 66 47 49 81 147 164 232 18 81 136 200 60 124 108 197 142 198 190 195 65 178 104 187 22 81 181 219 183 199 186 191 63 208 31 223 76 200 106 136 70 210 33 109 72 218 209 211 12 206 80 155 157 170 192 197 84 229 106 144 164 200 64 198 108 227 25 122 106 217 60 80 67 193 155 162 41 125 85 142 76 92 80 217 81 234 7 192 7 52 126 175 14 232 40 113 152 227 58 116 115 206 76 182 15 161 54 68 71 139 90 232 150 152 159 196 95 179 6 169 12 205 164 188 25 216 159 207 36 186 58 152 16 99 106 180 74 131 34 149 142 169 106 203 3 38 208 224 22 180 159 164…
Output: NO

Constraints:

1 <= n <= 2733; 0 <= m <= 5466; self-edges make the answer NO.

Loading...
Test Cases:No test cases
No test cases available.
Last roads of Dante - MEDIUM Coding Problem | CodeTikki