CT37275

Yami's roads Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Yami found an old ledger of roads in the print shop attic at the mushroom groves of Fungaldeep. The margin notes pose a precise question. Task: Edges u -> v mean u must come before v. Print the lexicographically smallest valid ordering of the n jobs (space-separated), or IMPOSSIBLE if a cycle exists. Input format: First line: n and m. Next m lines: u v. Output format: Print the order or IMPOSSIBLE. Constraints: 1 <= n <= 3200; 0 <= m <= 3200.

Example 1:

Input: 547 2176 110 438 302 349 438 527 170 450 388 442 168 505 159 308 166 470 22 230 321 484 25 365 80 87 175 280 179 357 290 461 184 447 362 424 256 447 432 518 114 338 204 212 171 441 18 96 237 439 292 358 410 480 113 316 65 231 181 330 69 120 229 482 21 348 177 407 119 298 210 465 262 501 115 371 123 437 254 326 156 252 350 382 197 458 57 507 376 466 161 285 98 364 141 543 26 500 185 226 115 322 23 206 202 492 300 538 421 519 325 360 151 319 161 385 205 415 99 450 335 407 328 469 347 520 443 502 118 438 189 516 371 525 61 184 186 525 68 283 115 434 232 546 51 463 9 32 444 473 83 310 55 113 183 273 384 385 12 148 36 380 198 432 34 196 171 432 212 443 99 512 208 286 60 363 133 490 241 348 200 314 427 499 134 374 163 503 87 446 319 459 28 77 47 209 49 544 91 154 240 328 251 524 177 253 111 223 …
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Example 2:

Input: 3057 1409 925 1249 818 2429 95 2360 1028 1582 1852 2198 1003 2065 2054 2732 431 742 1163 2487 2493 2919 485 1466 181 748 222 2774 371 1070 26 184 481 2314 286 2573 587 2846 399 2554 100 1391 1940 2083 96 412 650 983 429 1913 375 2187 313 624 1019 1850 347 1316 2519 2814 490 1973 1409 2041 1228 2658 948 2644 779 2941 511 2192 1334 1719 325 2021 528 2222 95 685 1439 2025 43 2477 516 2669 1643 2302 1080 1852 206 3018 2315 2445 446 2741 774 2470 87 2307 1677 1764 500 1412 1011 1250 1569 2882 2613 2989 1131 1538 411 693 1029 1918 1201 2158 46 2551 293 2555 1477 2185 615 2048 2039 2058 684 2078 1143 2884 540 1111 2883 2966 471 2082 958 1640 1827 2432 374 689 98 1616 1060 1381 133 2466 1338 2410 2583 2741 257 297 218 1476 806 2634 523 1505 572 2743 158 1445 2223 2306 2035 2308 1388 2544 2476 2954…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Example 3:

Input: 1397 2545 263 457 571 650 317 376 877 1343 358 924 514 1177 151 344 418 968 728 968 526 876 400 987 882 1313 125 807 722 1378 245 683 152 388 113 228 522 807 317 793 676 1333 115 194 535 886 459 1224 194 420 645 1353 711 1223 485 1089 279 594 47 1046 1113 1390 66 808 757 1371 65 1070 147 690 675 854 804 878 435 622 413 796 179 940 1229 1231 636 1278 468 1110 367 1280 79 109 375 1385 134 573 239 645 351 995 903 951 862 1158 307 1057 180 348 720 843 1066 1231 82 257 456 889 431 994 1157 1226 787 903 141 508 86 130 433 534 1115 1126 269 342 91 1066 1077 1195 159 716 291 535 1080 1282 828 925 407 960 702 1365 748 951 663 1377 2 1177 447 699 275 892 578 1213 882 998 81 1359 461 973 585 741 936 1167 394 1069 802 823 117 547 424 686 9 1201 177 1271 313 436 584 1374 39 679 106 1371 24 368 147 1182…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 …

Constraints:

1 <= n <= 3200; 0 <= m <= 3200.

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