CT50392

The Build Order of Duskwood

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the frontier camp of Duskwood; Hestia weighs the day's corridors manifests and starts the calculations. 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 <= 3278; 0 <= m <= 3278.

Example 1:

Input: 744 349 7 14 36 355 81 699 137 742 111 328 270 705 466 723 196 610 13 539 457 516 16 582 198 426 437 676 193 261 40 260 28 205 400 446 7 168 43 465 111 358 18 108 45 139 210 587 165 337 133 642 46 110 130 538 76 705 255 495 50 482 209 345 238 402 202 355 25 353 217 579 49 656 87 613 118 327 471 728 287 696 451 595 83 219 561 715 205 395 420 603 112 679 90 398 215 387 238 422 268 530 515 591 35 62 3 567 127 219 379 399 257 612 241 563 195 609 103 411 65 570 91 446 359 541 191 535 75 233 190 233 80 353 176 486 242 465 207 563 121 173 177 392 27 218 87 524 99 110 161 410 491 666 508 621 370 693 246 662 258 326 173 620 412 597 228 699 371 551 671 679 93 679 164 554 252 283 276 311 183 311 466 661 255 445 75 403 406 705 74 421 271 371 112 469 215 258 252 549 6 470 291 553 325 603 27 107 144 606…
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: 2825 3035 1110 1872 676 1675 61 2663 494 2227 42 501 1776 2216 1696 2250 197 586 272 1854 44 2682 298 558 716 2774 562 1648 630 723 1544 1613 375 1231 2261 2449 180 1867 743 2717 799 1090 471 2487 37 518 133 1744 884 1249 2274 2532 721 1638 527 2447 615 2440 882 1697 849 1772 264 2001 687 2352 1424 1630 45 2039 839 2487 190 981 715 2450 1618 2273 1334 1930 1484 2471 2323 2510 275 2068 406 752 1211 2144 2093 2565 559 1913 373 431 1737 2805 376 1714 925 1896 939 2074 228 1307 1694 1826 977 1522 2261 2561 983 2497 1221 1423 183 526 1185 2470 670 1363 717 2509 2112 2503 2376 2788 801 1093 1244 2414 1504 2641 45 2101 1602 2638 2385 2511 2111 2228 998 1157 969 2519 470 1725 383 2203 606 1053 1631 2721 15 475 323 2265 942 1759 965 1506 174 1789 1666 2754 2041 2570 20 2404 737 1859 1520 2424 1323 …
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: 877 1208 180 690 340 871 674 788 365 424 15 75 35 433 270 500 17 298 181 293 185 620 365 565 452 557 415 859 70 230 257 847 263 308 240 316 81 629 71 397 318 479 471 581 114 173 37 747 113 601 320 677 454 462 314 721 127 283 311 674 220 796 248 686 214 453 389 416 29 139 68 101 471 785 130 533 547 785 388 508 199 873 419 822 126 374 29 296 283 498 118 383 174 266 67 238 330 669 589 616 9 273 468 728 58 456 565 761 562 727 74 132 96 533 197 284 587 752 715 770 44 516 611 745 367 645 386 520 563 787 248 573 271 541 186 792 492 873 238 435 178 274 117 331 193 307 505 779 35 51 33 428 137 287 240 744 339 847 578 862 218 836 117 785 50 868 541 805 280 671 11 422 414 572 665 873 3 706 368 812 281 707 289 444 116 252 487 660 39 244 24 810 1 845 242 870 279 581 19 205 242 315 317 839 386 490 81 65…
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 <= 3278; 0 <= m <= 3278.

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