CT53110

The Build Order of Scriptoria

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the ink district of Scriptoria, Nandini the cartographer keeps careful count of the canals. Document the rare sighting, every figure matters. 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 <= 2644; 0 <= m <= 2644.

Example 1:

Input: 2477 1334 309 764 298 2348 508 1170 419 1940 60 216 433 2400 336 1292 963 2020 1210 1965 331 1393 1243 1735 2222 2273 1764 2131 1388 1538 168 1687 440 802 654 1467 380 2149 563 1539 608 851 1797 2097 526 2442 728 2428 1411 1767 1486 2123 317 2356 165 783 1267 2067 688 1095 1546 2301 735 1294 987 1387 2117 2257 524 1041 113 981 183 385 1325 1381 724 1099 775 1467 1126 1516 785 1549 2029 2358 224 1777 293 386 1129 1183 1584 2395 41 1015 381 561 839 2195 161 1727 1782 2392 2029 2373 8 1789 202 1544 1193 2033 942 2249 934 1744 957 1345 1178 2112 926 1684 838 2340 1301 1526 1609 1695 1081 2440 896 939 1486 1726 1429 1654 250 1545 491 2243 1323 2291 734 1253 1391 1753 952 2043 1051 1347 1840 1989 2040 2213 653 2196 700 1066 520 1018 1196 2063 572 2162 1205 2189 850 1099 830 1810 1635 2201 538 19…
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: 644 1990 244 407 154 293 297 523 390 497 46 103 91 479 11 128 65 134 231 234 76 637 259 318 34 158 398 638 447 556 120 567 199 373 519 616 303 588 112 487 109 474 386 387 225 543 302 591 423 548 34 64 48 369 51 553 360 365 293 592 256 516 588 643 59 320 18 100 170 383 206 617 369 469 30 141 156 482 545 626 438 512 279 391 78 643 105 594 404 475 521 522 234 488 158 254 218 479 411 506 252 417 154 211 107 466 239 455 400 454 174 341 100 513 62 254 66 522 298 426 472 527 94 167 83 499 102 265 587 612 326 547 56 134 24 326 387 552 83 606 82 250 532 599 299 625 30 551 4 416 195 313 385 574 73 629 306 540 361 603 423 603 422 474 236 413 82 417 21 154 65 338 331 443 269 438 357 383 129 496 189 567 242 431 2 469 11 209 492 562 145 154 104 384 230 448 101 138 224 504 233 320 16 445 182 293 41 504 7…
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: 691 1204 210 382 255 472 204 257 483 584 51 316 165 487 486 556 473 589 416 522 2 557 28 684 132 652 152 378 4 16 64 545 182 545 17 319 320 499 289 301 115 585 56 285 357 388 361 543 173 191 412 501 247 264 479 555 266 303 301 337 269 587 147 497 236 323 2 366 192 310 116 676 184 466 81 392 35 165 375 583 190 390 12 335 46 127 212 517 70 218 588 631 328 504 353 446 138 152 140 587 425 639 270 523 153 213 331 369 104 169 185 646 20 206 95 428 90 562 249 675 206 457 348 540 551 661 37 118 9 533 3 9 100 131 1 610 271 560 442 625 222 389 448 548 463 612 80 352 121 654 10 139 227 459 45 557 602 641 35 55 135 445 355 657 120 344 85 103 54 210 268 523 25 272 338 574 550 558 308 348 315 369 403 453 88 357 431 676 21 516 84 87 57 636 178 624 198 329 173 302 497 683 238 315 92 430 95 195 167 199 31 …
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 <= 2644; 0 <= m <= 2644.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order of Scriptoria - MEDIUM Coding Problem | CodeTikki