CT54378

Keeper's tunnels Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the salt flats of Palemere, someone must plan the festival budget. This year the task falls to Keeper, 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 <= 2876; 0 <= m <= 2876.

Example 1:

Input: 521 190 13 299 76 480 96 379 148 392 48 243 59 111 265 385 133 457 443 490 312 429 118 428 264 306 351 485 146 354 264 369 92 175 64 329 125 492 106 448 248 369 140 463 77 141 330 506 325 326 20 483 325 462 287 452 4 134 75 388 41 316 81 205 198 216 35 519 128 146 50 73 25 394 52 117 182 458 17 83 18 261 103 464 192 262 369 500 279 486 311 445 126 201 343 521 234 245 162 501 378 380 310 344 36 71 245 333 245 405 56 462 11 429 14 516 17 163 57 327 173 269 183 289 9 134 391 408 109 122 419 493 111 232 213 352 236 452 164 463 130 409 350 492 84 247 170 436 46 193 224 288 82 317 229 482 242 396 283 519 356 441 13 241 42 411 144 161 292 347 35 169 17 384 329 462 74 123 279 306 429 481 320 404 170 335 232 500 239 472 140 475 168 271 226 403 54 209 14 234 78 307 120 273 186 226 228 316 224 354 45…
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: 522 2153 213 440 2 230 151 170 1 386 59 225 121 126 502 504 43 177 361 412 170 513 142 181 249 320 106 204 155 181 265 476 344 388 85 484 258 435 64 246 318 441 17 308 187 458 371 382 36 515 136 329 94 415 288 471 11 394 160 190 152 290 278 399 14 266 244 320 58 488 216 288 221 254 200 263 279 461 219 322 126 321 170 408 454 502 89 322 257 465 377 474 271 458 22 522 345 413 223 506 339 493 63 501 96 164 22 357 81 481 79 521 164 471 213 446 86 502 16 135 135 267 244 466 136 482 419 487 86 240 35 336 217 316 62 404 128 458 50 53 486 497 68 357 80 433 130 221 16 210 98 290 110 341 383 497 347 401 14 119 30 280 409 414 292 412 88 320 15 234 338 418 65 384 183 439 313 388 132 142 453 478 521 522 269 406 235 298 380 430 32 314 137 464 203 255 17 181 228 487 240 264 34 266 255 259 6 522 53 232 25…
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: 2635 1900 1883 2248 205 2264 789 1665 78 2129 250 1956 64 2587 2143 2588 2131 2480 1199 1447 101 1927 2316 2411 775 1413 1427 1805 2424 2513 1267 2122 1892 2366 416 2615 1825 2207 267 1667 214 2452 204 1085 835 1831 261 1601 1488 1520 814 1120 1073 2341 11 1875 1878 2283 129 778 547 944 2450 2561 66 119 765 2196 393 791 770 1297 898 1109 393 483 450 2627 1613 2380 775 2378 812 1885 1214 1262 150 1477 448 1957 298 531 1591 2255 448 1453 1097 1770 165 2164 19 604 144 1759 228 2135 1926 2316 61 1544 638 1822 259 1452 1526 2066 2250 2257 175 713 141 1606 499 807 516 2604 2185 2565 1223 1940 105 501 1281 1739 2108 2455 121 2246 221 696 381 2263 386 2091 1090 2215 586 964 159 765 1483 1947 206 395 34 1838 348 2341 261 992 872 2566 380 2347 2394 2481 1356 1970 1107 2005 648 1959 169 1204 1666 191…
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 <= 2876; 0 <= m <= 2876.

Loading...
Test Cases:No test cases
No test cases available.
Keeper's tunnels Build Order - MEDIUM Coding Problem | CodeTikki