CT46712

The Winterholt Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the snowberry thicket of Winterholt with crates of tunnels, and Elowen the store warden must account for every last one. 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 <= 1615; 0 <= m <= 1615.

Example 1:

Input: 509 1146 93 359 7 377 270 331 67 81 99 285 166 419 255 458 288 465 148 407 175 262 179 395 153 212 148 212 197 476 191 480 90 475 315 472 441 454 138 499 265 401 180 281 172 270 60 469 99 402 323 449 229 419 463 499 75 400 210 282 64 411 122 359 64 171 167 223 32 215 281 483 27 502 36 96 277 419 401 482 336 346 75 327 159 223 281 342 389 485 15 281 143 473 41 352 273 477 87 328 104 441 52 255 41 483 241 435 218 418 89 409 354 480 125 377 346 385 205 444 97 274 447 505 363 440 40 482 60 217 362 395 222 451 78 170 151 331 160 408 121 351 48 70 69 331 113 394 300 305 154 238 109 290 61 311 231 320 354 400 241 243 272 492 305 344 196 281 160 477 280 481 178 363 40 290 339 475 173 289 242 323 15 403 284 300 256 294 49 253 382 388 132 376 331 420 297 414 89 438 37 339 5 354 213 468 184 447 57 14…
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: 1148 952 602 684 779 1011 653 933 575 983 594 908 655 735 371 1046 41 914 53 279 168 791 277 778 357 670 363 944 563 641 630 1007 800 882 393 1009 96 1052 34 100 259 489 373 683 738 962 61 192 185 1053 101 752 32 906 113 1048 1053 1126 148 279 38 804 58 758 327 992 230 552 345 843 666 767 142 550 193 389 652 1024 502 1075 658 999 481 1147 655 723 872 1082 739 1111 221 342 475 998 613 820 82 725 296 786 31 432 552 580 455 960 6 123 612 867 355 902 61 186 324 375 402 953 824 979 254 510 287 514 480 534 489 660 381 426 132 449 813 814 536 895 597 683 70 250 764 892 285 1010 434 1024 596 1128 644 659 587 690 302 311 867 874 482 1144 661 1047 74 646 705 865 66 1000 137 916 463 588 50 412 10 21 663 915 11 1148 686 994 726 841 126 713 1044 1068 293 569 738 1131 758 967 458 728 660 874 216 1114 81…
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: 346 366 240 272 48 75 27 280 98 336 91 128 23 108 16 290 126 341 140 165 41 223 95 124 130 230 36 295 3 172 110 245 313 324 174 188 26 234 51 132 62 261 91 256 152 184 51 168 96 334 43 206 31 110 3 80 163 188 63 345 13 146 28 99 7 68 116 280 45 304 75 215 94 189 171 178 77 241 71 106 55 189 150 238 16 117 12 293 57 327 86 214 153 253 97 101 39 261 15 100 14 286 53 95 105 276 226 335 256 321 23 71 38 195 65 109 146 210 212 282 154 192 244 266 175 228 197 327 24 252 24 307 149 224 84 117 1 333 239 342 140 249 176 197 222 286 115 218 77 267 49 280 121 213 44 86 303 336 156 320 232 235 236 289 226 244 267 341 176 189 26 100 41 91 200 249 105 144 101 198 107 169 138 281 100 196 147 187 180 258 109 193 166 222 3 30 184 330 27 289 128 220 29 307 194 198 23 205 130 189 224 300 79 299 111 127 13 16…
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 <= 1615; 0 <= m <= 1615.

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