CT36640

Zara's Ledger of corridors

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Zara the surveyor watches over the ember mines of Cindercrag's stores of corridors. A careful computation stands between order and chaos. 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 <= 1971; 0 <= m <= 3942; self-edges make the answer NO.

Example 1:

Input: 1666 3028 1 2 2 3 1 3 1091 1532 263 524 51 816 172 865 201 977 1398 1509 188 1422 211 1362 1230 1283 790 1572 1084 1242 22 226 387 1583 110 1656 1122 1384 934 1284 413 437 231 696 1059 1213 37 1286 314 1308 322 987 48 1306 423 777 351 525 1010 1036 47 265 309 1118 437 1535 1030 1328 403 707 1166 1621 1012 1570 462 1188 69 102 1238 1331 301 1248 405 997 83 1137 979 1490 575 1192 1308 1648 244 308 655 793 125 885 640 987 21 1295 477 995 314 881 248 437 78 114 63 707 549 771 441 863 472 1472 759 982 688 901 380 1142 531 898 974 1465 226 1169 605 862 254 1454 122 357 107 1558 123 598 751 971 452 1551 55 1606 240 899 750 1319 1057 1653 717 1230 657 905 811 1507 770 1138 303 834 1019 1633 153 439 88 679 104 1633 390 1320 577 1298 1127 1137 597 1588 183 1536 420 1072 917 941 149 873 62 571 605 82…
Output: NO

Example 2:

Input: 479 587 264 478 139 469 371 412 8 453 242 406 208 371 51 458 49 467 52 328 29 133 404 426 155 158 402 452 4 431 164 406 35 121 33 126 92 356 137 207 150 337 206 250 314 446 57 121 325 393 113 194 351 369 132 144 187 213 267 427 94 144 241 255 2 140 293 362 324 327 163 332 175 202 182 421 112 398 303 319 68 227 122 270 120 207 295 376 232 339 164 187 58 308 221 400 154 160 14 35 423 429 162 451 63 134 170 306 101 139 122 301 156 218 32 323 83 98 68 432 44 261 408 441 180 458 253 352 147 415 153 300 270 446 227 356 43 213 335 361 47 316 47 332 57 66 354 456 266 346 60 459 153 426 61 331 396 402 18 473 227 455 108 117 145 290 119 246 88 182 228 339 175 394 57 387 58 236 15 355 19 120 49 199 207 352 198 210 400 438 67 227 75 208 42 317 53 312 118 168 69 230 187 443 180 473 401 476 255 369 168 …
Output: NO

Example 3:

Input: 56 267 23 55 31 52 20 56 7 51 28 29 41 55 37 46 27 48 42 55 17 40 1 30 5 17 5 47 34 48 5 36 3 26 8 20 45 51 44 55 5 9 30 31 12 29 5 20 21 51 14 27 26 47 6 55 33 41 28 56 3 56 16 41 9 39 20 35 13 31 5 31 7 28 36 40 30 34 24 46 8 9 32 46 27 28 19 38 1 27 34 38 2 38 26 31 10 36 16 47 3 36 42 52 37 48 6 12 25 43 16 52 18 48 27 33 35 49 12 50 38 55 37 43 11 53 9 36 16 37 25 31 21 39 5 27 18 30 21 23 13 51 4 14 14 38 33 53 12 20 4 19 21 34 51 56 31 41 46 55 5 39 36 38 7 26 18 50 3 5 13 40 2 51 9 46 23 24 13 14 15 42 28 34 2 56 10 56 23 30 12 40 2 26 24 53 35 45 6 19 24 41 26 36 7 49 12 43 9 28 34 45 16 17 13 16 8 43 29 45 2 19 10 28 24 28 4 7 13 53 20 55 2 50 10 40 48 49 8 41 13 47 10 27 24 32 10 11 23 49 5 21 19 28 4 53 8 33 8 11 37 56 38 51 10 26 23 53 22 41 7 19 7 33 11 55 6 38 17 20 29 43 8 …
Output: NO

Constraints:

1 <= n <= 1971; 0 <= m <= 3942; self-edges make the answer NO.

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