CT38359

The Build Order of the Moonlit tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the sulphur springs of Brimstone pays by the answer, and Tracker intends to earn it. First: the full register of tunnels. 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 <= 1148; 0 <= m <= 1148.

Example 1:

Input: 445 445 256 271 199 218 102 103 158 374 301 334 109 227 52 328 342 427 77 86 206 368 268 379 281 363 16 180 55 145 39 175 14 342 10 137 70 286 385 387 66 377 230 381 115 344 114 435 101 169 273 305 179 362 73 251 32 247 113 132 107 337 40 164 221 289 207 210 210 258 103 237 1 298 1 117 206 231 80 254 82 96 384 396 43 249 223 268 305 408 108 395 226 378 21 185 289 358 199 392 50 82 91 285 131 329 90 315 157 322 45 398 293 385 3 377 435 444 302 358 107 348 216 407 270 434 32 129 117 184 85 177 11 237 168 328 37 86 205 334 114 383 229 337 79 168 269 374 208 343 101 426 163 319 60 266 286 356 103 204 75 269 203 265 23 385 44 75 73 89 69 110 332 389 179 225 373 401 259 279 50 396 264 407 169 226 59 136 146 167 44 163 240 418 430 432 367 412 58 128 277 362 162 410 255 262 118 137 99 443 235 304 …
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: 678 286 211 392 266 547 441 619 286 439 348 673 97 236 373 635 47 222 51 452 215 387 136 371 232 536 271 362 66 437 291 604 62 148 210 402 169 486 23 344 137 156 409 596 314 541 270 466 228 326 7 357 219 467 242 637 408 593 60 531 79 210 253 507 380 660 371 390 217 238 182 632 87 584 107 562 448 475 406 516 252 328 285 335 377 446 287 564 622 633 89 471 45 425 34 69 106 499 461 569 107 181 259 277 121 130 342 531 55 400 52 264 344 549 37 628 94 155 327 578 556 583 234 651 470 552 31 626 239 552 310 401 358 503 131 454 168 587 350 568 144 556 171 583 293 657 53 462 71 487 391 531 482 556 239 333 506 667 115 135 86 653 400 503 437 447 83 629 351 380 61 237 177 361 7 532 477 569 282 339 166 550 153 212 249 427 568 608 455 497 328 616 51 98 133 399 9 343 323 380 18 248 93 123 2 27 89 293 331 5…
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: 143 331 61 97 7 14 48 129 8 28 34 121 124 143 67 134 55 133 54 96 32 143 82 134 25 52 38 143 17 79 91 128 1 128 36 69 33 85 61 118 137 142 17 131 92 117 11 130 40 132 62 99 67 72 43 58 61 142 70 102 79 138 53 57 110 133 23 74 68 91 60 73 22 52 72 89 66 107 21 128 1 138 23 89 89 130 21 23 72 107 65 88 5 27 16 122 1 90 17 88 23 38 3 39 59 98 54 102 30 142 7 39 46 107 29 56 10 36 27 128 60 125 65 119 100 109 18 53 98 139 108 135 73 77 22 72 128 136 47 66 35 119 22 38 10 19 6 76 60 127 21 63 6 46 8 138 7 37 96 110 48 51 86 136 19 65 44 85 13 34 57 120 13 79 142 143 23 39 22 62 40 51 105 121 4 124 64 110 2 70 119 127 19 82 43 50 29 93 112 143 41 86 65 67 101 112 15 135 34 81 61 129 75 126 57 86 30 99 56 128 65 126 49 143 78 134 98 109 6 137 3 33 36 45 34 48 92 124 52 141 31 130 49 124 7 19 3 61…
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

Constraints:

1 <= n <= 1148; 0 <= m <= 1148.

Loading...
Test Cases:No test cases
No test cases available.