CT40515

Aria's Ledger of canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the fjord village of Deepwater, Aria the auditor keeps careful count of the canals. Approve the repair estimates, every figure matters. 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 <= 1266; 0 <= m <= 2532; self-edges make the answer NO.

Example 1:

Input: 663 784 1 2 2 3 1 3 53 192 159 633 180 360 320 379 219 299 188 263 185 636 319 341 326 332 111 462 335 536 180 249 51 249 47 639 307 641 402 604 246 596 45 135 201 473 154 195 14 65 316 562 417 489 559 625 420 577 43 93 219 267 247 401 586 592 250 594 214 459 113 456 49 290 27 282 540 660 188 532 14 593 109 140 104 129 186 458 630 651 172 641 449 458 97 172 65 121 141 154 243 508 194 641 90 526 333 592 79 646 446 546 400 556 91 242 61 593 269 358 339 425 242 379 6 604 273 380 255 338 101 384 103 203 589 623 76 272 56 616 120 340 390 395 170 316 186 190 241 451 136 332 185 527 515 598 145 281 136 254 119 176 195 319 358 641 357 513 69 409 441 631 153 203 256 410 200 529 130 272 162 552 269 566 35 255 555 639 116 294 154 662 5 639 428 455 59 499 110 168 323 327 44 460 243 491 134 642 75 146 …
Output: NO

Example 2:

Input: 1173 970 984 1097 933 1107 1001 1065 240 535 155 704 250 917 581 804 27 884 425 1048 148 450 472 578 234 473 132 413 69 931 574 647 186 542 483 1073 333 427 116 176 262 745 503 708 426 468 216 773 70 132 588 958 869 917 279 471 540 860 688 886 988 1144 1009 1040 450 1018 27 415 79 137 252 494 801 976 1055 1111 474 951 85 140 157 248 274 1098 11 909 724 760 219 851 345 710 27 85 1116 1160 582 768 108 831 931 1160 309 1069 212 723 780 1087 226 806 958 1082 268 528 21 53 128 464 756 828 80 1079 221 566 269 500 325 793 180 422 768 1120 234 400 643 893 414 1110 126 659 453 1034 15 657 600 855 143 473 302 648 1054 1099 300 1037 356 808 506 832 894 1071 946 1060 560 590 745 1130 883 1167 278 413 119 1169 134 207 574 784 334 838 283 414 226 1034 797 900 705 1164 311 1146 32 337 336 827 345 896 99 …
Output: NO

Example 3:

Input: 336 270 26 126 267 281 170 174 272 278 294 320 188 318 190 264 41 121 70 114 80 231 145 257 216 221 173 230 144 145 301 310 58 67 6 97 169 209 29 81 108 322 80 210 144 188 273 330 217 256 32 264 14 324 18 183 28 238 137 229 13 194 125 322 112 114 196 286 89 211 132 310 126 238 218 300 168 204 5 172 58 252 151 181 230 249 155 286 69 101 175 219 31 107 33 332 8 34 39 146 256 313 20 329 107 284 242 285 294 330 110 264 51 161 39 188 165 188 100 212 56 331 172 267 65 228 124 174 166 286 96 204 22 152 8 67 9 183 94 126 1 268 208 259 5 218 167 247 2 174 145 329 269 318 66 334 2 260 46 208 132 334 107 329 121 192 171 202 155 274 214 268 161 175 123 221 91 139 260 266 114 241 83 138 77 276 1 79 179 185 33 103 52 319 13 47 24 302 58 139 167 259 32 78 233 240 21 152 32 221 168 309 105 239 280 320 101…
Output: NO

Constraints:

1 <= n <= 1266; 0 <= m <= 2532; self-edges make the answer NO.

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