CT36782

Rhea and the Two Guilds

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Rhea inherited the loft at the bamboo terraces of Verdantstep 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 <= 3340; 0 <= m <= 6680; self-edges make the answer NO.

Example 1:

Input: 1225 5068 1055 1114 197 1205 127 1193 289 685 745 956 161 175 829 1075 833 1209 693 903 140 446 617 1176 511 534 210 1110 229 355 567 1038 224 1112 347 355 514 844 375 1119 537 1179 598 948 167 257 277 916 66 171 63 733 264 285 169 1111 556 806 276 380 149 519 801 1079 6 627 51 611 830 868 82 422 262 333 5 682 771 1127 728 957 719 896 208 373 884 1028 1120 1216 487 1195 11 906 717 795 306 1111 105 277 17 1121 130 373 153 365 197 1072 111 256 948 1049 496 971 146 1090 425 520 300 982 940 1122 458 566 158 876 772 974 862 1028 344 1127 661 1068 125 880 517 588 798 860 341 762 30 140 113 1081 36 198 926 996 680 690 1050 1116 150 1025 775 1219 188 573 11 528 679 864 176 844 112 273 540 1176 449 666 561 1184 16 1100 627 760 97 1062 634 1026 246 1216 56 130 574 836 125 704 284 1028 305 1032 559 6…
Output: NO

Example 2:

Input: 2758 1870 1 2 2 3 1 3 694 1028 1702 2066 784 1179 449 1558 1197 1230 920 1733 291 672 427 2265 2123 2214 325 1087 439 1573 2104 2445 1210 1325 2371 2412 394 2062 1516 1683 754 2755 288 2110 401 2287 2515 2590 878 2732 539 756 1660 2045 653 1210 899 2035 565 646 1065 2612 99 2564 469 1816 545 2519 537 2590 1081 1489 1725 1814 1155 1180 1415 2267 2089 2456 216 2225 1668 2607 1045 1226 812 1210 423 2668 837 1032 144 909 402 648 1461 1639 679 1600 1734 2405 914 1621 71 2371 385 2204 2414 2750 1384 1927 1124 2655 494 2618 1866 2514 1565 2348 90 2276 1657 2019 1782 2279 789 2583 483 2573 1699 2054 176 682 1576 2018 548 2758 1348 2343 70 256 20 1827 343 393 2 2701 2584 2734 683 2268 931 1555 1854 2144 2352 2635 2103 2638 1610 1949 2478 2746 272 750 929 1126 372 1448 212 2116 836 1723 505 1342 142…
Output: NO

Example 3:

Input: 386 5494 1 2 2 3 1 3 106 235 84 379 282 373 164 304 124 317 33 125 22 150 46 353 28 353 173 339 314 352 17 145 1 106 262 314 93 127 231 277 203 337 248 254 54 362 2 145 246 380 116 297 46 291 197 359 64 319 250 269 164 200 360 362 170 286 109 257 15 251 153 156 188 290 105 345 3 20 89 224 226 305 75 306 320 386 244 281 74 385 297 340 152 349 159 193 142 164 171 208 51 320 128 140 179 256 37 255 15 242 191 324 367 379 66 91 44 328 139 265 320 328 188 337 249 315 6 156 86 206 175 247 106 365 177 211 212 330 62 174 146 181 105 380 18 149 35 356 135 262 175 272 30 105 113 209 142 312 31 214 153 219 29 248 17 266 153 173 119 352 289 384 235 274 75 160 42 219 132 155 182 309 99 139 156 276 20 289 53 291 54 152 36 375 112 328 187 221 286 308 48 239 227 257 359 374 100 304 83 357 38 309 185 301 24…
Output: NO

Constraints:

1 <= n <= 3340; 0 <= m <= 6680; self-edges make the answer NO.

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