CT60273

Cartwright's Two Guilds Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Cartwright found an old ledger of tunnels in the kitchen attic at the quays of Driftwood. 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 <= 2922; 0 <= m <= 5844; self-edges make the answer NO.

Example 1:

Input: 321 3294 126 195 111 134 271 274 102 239 84 189 29 316 140 164 116 198 94 276 37 250 144 146 21 198 215 240 120 221 46 138 28 34 64 191 70 156 77 223 160 296 25 169 251 298 82 284 114 185 48 90 21 268 18 256 137 144 68 139 89 165 27 56 171 287 14 296 64 163 15 211 35 306 14 292 28 223 6 316 101 168 19 69 115 180 222 303 166 222 122 244 239 275 95 231 50 111 66 179 67 87 175 230 159 205 173 217 8 45 22 138 171 315 142 157 44 279 66 180 205 257 37 51 15 319 105 318 5 213 53 117 34 165 104 298 40 244 106 219 131 138 73 289 211 285 6 160 22 108 206 282 167 203 2 118 167 176 253 268 39 189 255 257 166 182 88 209 55 109 165 321 70 305 189 214 105 193 81 303 5 248 163 310 122 123 204 283 265 271 25 312 148 152 191 223 10 144 46 194 219 300 147 231 43 154 150 171 221 249 1 191 167 282 2 303 62 287…
Output: NO

Example 2:

Input: 2785 5627 1 2 2 3 1 3 1042 1409 1640 2474 756 1377 601 1632 673 1263 1213 1236 1222 2784 1089 1171 1729 1732 1966 2264 40 431 218 1958 1307 2293 1565 1797 103 400 991 1917 93 2135 1609 2767 136 1778 825 1471 1508 2345 118 950 962 1495 969 2512 1313 1466 2140 2209 942 1251 1599 2197 1220 2052 818 1325 824 2465 995 2104 1069 2538 8 1587 1647 2064 1153 1296 1897 1916 257 1287 276 2481 360 515 569 1533 1619 2284 578 2737 852 997 127 1970 15 2545 1445 1767 312 1179 1493 1676 1529 1722 345 1333 162 1814 1911 2125 231 1131 193 2281 1396 2266 918 2121 414 438 379 1793 1609 2419 601 2364 993 1043 1276 2661 1446 2669 232 1734 963 2724 1565 1662 571 2594 605 2301 1486 2460 1722 2297 1230 1739 71 515 1272 1498 26 2313 803 1840 1637 2110 1492 1932 721 1574 344 1815 278 1299 158 2365 952 2527 1292 1723 …
Output: NO

Example 3:

Input: 1357 4385 458 537 210 922 520 655 322 1156 721 1282 104 136 21 1319 534 963 1062 1227 62 1142 1102 1334 1133 1260 1006 1125 20 1185 461 1053 625 784 540 1258 1249 1285 781 1193 159 621 1062 1207 626 1077 452 1128 578 852 213 1222 409 719 965 972 247 380 969 1247 368 434 795 1139 341 938 606 920 409 665 154 191 660 983 447 894 169 182 150 741 659 996 141 161 196 326 621 974 967 1205 896 1196 388 1008 457 823 99 364 240 452 91 1163 455 506 339 1067 550 1293 55 1213 658 1134 1135 1353 418 597 551 1003 995 1103 819 972 92 694 311 657 193 605 285 932 391 1196 794 998 891 986 907 1193 276 456 61 402 530 536 413 633 11 243 376 1222 498 1003 568 1109 11 951 157 1240 909 913 1110 1206 61 141 28 743 829 1185 22 426 87 130 38 757 460 684 224 954 5 1037 897 1273 89 483 464 1236 45 1081 21 85 311 1325 …
Output: NO

Constraints:

1 <= n <= 2922; 0 <= m <= 5844; self-edges make the answer NO.

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