CT52043

The Twilight tunnels of Dante

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the granite steps of Stonehallow, someone must settle a dispute between crews. This year the task falls to Dante, armed only with the tunnels register. 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 <= 2340; 0 <= m <= 2340.

Example 1:

Input: 984 338 501 742 897 946 378 796 153 694 62 64 21 509 367 539 493 901 81 486 536 570 192 450 185 702 510 736 208 268 8 820 449 933 472 492 593 886 373 593 429 696 19 278 145 256 141 286 2 735 203 637 52 459 594 733 827 947 594 732 701 799 294 626 452 783 745 935 94 812 461 643 184 321 302 800 198 575 152 895 189 509 269 426 97 579 106 426 335 598 74 168 489 592 573 726 34 926 345 429 450 807 146 913 865 902 131 760 315 463 327 656 720 855 13 832 171 255 235 454 211 332 271 721 963 975 559 621 45 315 258 832 67 547 193 584 487 896 397 593 517 684 469 505 464 593 128 350 29 362 211 783 532 904 398 667 288 647 271 811 299 780 433 892 744 869 114 597 101 606 283 758 416 579 338 887 505 556 442 907 368 871 9 331 610 701 304 595 809 914 37 211 612 706 236 762 668 866 47 745 142 429 128 399 194 71…
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: 371 679 132 169 183 363 106 162 96 174 240 308 168 281 46 179 28 126 94 238 160 182 69 155 52 283 15 125 153 347 72 302 156 228 105 241 172 318 93 120 29 149 201 353 181 355 34 157 2 332 174 246 219 371 11 203 39 368 212 219 212 325 94 129 114 325 96 259 36 353 71 149 271 367 116 187 80 226 77 309 3 26 107 157 54 371 339 367 134 256 219 357 138 238 247 252 74 291 16 97 235 279 25 257 127 193 6 199 201 248 144 236 111 151 162 293 107 197 18 346 87 185 26 207 193 265 166 280 229 270 329 343 131 163 17 318 78 260 71 357 329 358 53 263 113 195 251 287 6 144 87 98 118 311 21 54 169 170 76 306 42 95 5 146 139 275 57 224 45 196 78 232 193 271 43 225 167 168 2 233 88 108 261 358 234 246 14 300 54 169 177 345 15 33 201 223 11 14 69 220 65 314 252 344 337 361 171 189 39 160 5 18 36 234 93 365 238 26…
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: 1282 705 198 927 100 1013 376 1050 832 1226 460 812 55 398 30 1231 374 535 78 670 371 548 183 322 2 213 310 417 921 1082 904 1223 350 821 187 461 656 1261 802 1084 327 652 876 1033 257 335 340 463 519 803 850 887 307 484 539 596 316 797 669 1154 450 573 1085 1241 251 392 854 923 473 957 174 1252 48 607 757 855 191 411 278 973 949 994 6 7 253 1058 520 940 239 927 240 644 1119 1198 555 585 760 1134 1105 1134 487 1093 88 820 917 1160 330 524 382 815 29 854 497 640 649 658 300 1030 44 1163 477 571 185 907 99 449 211 941 332 516 414 1153 207 597 503 552 418 1082 217 1211 872 1132 28 570 276 1150 591 625 126 1276 507 738 247 993 21 532 167 993 789 1086 934 1071 19 120 782 1147 657 889 34 477 29 701 257 542 195 259 180 1195 755 1138 821 1061 292 368 182 317 421 1146 836 1154 188 311 7 493 229 748…
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 <= 2340; 0 <= m <= 2340.

Loading...
Test Cases:No test cases
No test cases available.
The Twilight tunnels of Dante - MEDIUM Coding Problem | CodeTikki