CT42792

The Build Order at Rye Hollow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ravi runs the foundry at the gristmill of Rye Hollow. Today the books show a list of corridors, and the numbers must be worked out before sundown. 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 <= 3033; 0 <= m <= 3033.

Example 1:

Input: 57 810 40 57 40 47 49 56 16 17 28 47 35 48 15 53 21 26 44 57 39 40 13 47 5 56 23 57 32 45 18 53 3 53 5 46 34 55 3 9 19 41 14 46 32 57 21 40 20 50 50 52 6 33 14 26 43 56 21 55 4 45 34 35 6 8 32 36 26 45 6 26 28 41 23 48 23 26 13 35 33 47 25 38 39 57 21 27 21 51 2 3 5 7 20 42 6 15 24 52 5 37 51 52 7 34 37 43 20 46 45 48 36 55 22 54 30 43 3 32 16 32 40 51 22 41 15 17 15 33 26 55 29 39 3 30 3 33 3 22 30 50 7 13 6 13 19 33 26 35 21 56 20 57 4 57 21 29 40 53 11 30 22 53 4 33 42 52 17 29 13 40 15 48 2 8 46 53 47 48 18 50 7 18 39 47 20 56 28 30 4 6 16 19 22 29 36 52 9 49 11 34 14 23 55 56 5 47 47 52 2 35 26 28 6 55 5 41 5 21 33 37 1 50 41 48 10 32 24 26 22 28 17 36 20 23 17 54 20 38 21 33 27 50 10 33 54 57 29 49 26 42 13 28 15 54 21 46 9 36 9 56 19 30 21 37 22 26 21 31 5 8 37 38 1 41 14 31 26 51 1…
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

Example 2:

Input: 668 2936 179 606 52 224 54 336 130 525 18 627 86 107 31 230 165 628 383 654 148 441 414 426 3 408 104 593 254 374 345 432 642 658 69 472 203 567 44 70 586 628 24 478 56 250 89 304 349 489 195 578 182 236 75 257 356 508 294 642 567 639 377 447 224 400 156 323 13 97 155 309 283 429 230 259 535 587 245 386 218 469 460 547 317 421 457 569 162 446 263 590 501 520 31 271 172 343 210 242 454 605 310 636 102 511 273 346 226 421 15 18 17 374 97 214 99 320 21 302 56 666 387 398 81 98 162 252 22 624 81 524 300 608 338 461 447 526 414 550 127 176 574 651 198 322 496 639 262 329 556 591 513 642 25 359 351 527 323 385 374 566 287 340 188 456 138 623 348 613 586 647 374 610 62 346 260 334 438 542 192 597 353 593 172 323 48 506 572 599 180 566 179 511 448 631 222 406 410 545 337 402 50 158 98 177 193 299 …
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: 425 414 34 279 232 325 78 267 121 195 109 218 254 419 116 318 49 345 295 301 10 379 52 221 77 90 57 223 276 363 285 398 19 56 6 374 234 401 333 400 99 171 258 347 323 409 64 79 108 146 313 379 351 419 294 305 104 194 321 406 14 337 14 152 178 262 217 301 199 344 204 217 173 336 279 376 21 386 39 134 94 233 36 416 159 412 206 363 45 53 252 405 95 403 102 348 23 239 266 296 255 330 294 392 189 400 284 315 120 229 280 424 228 288 9 174 45 334 57 76 251 259 72 136 107 209 302 368 210 370 251 350 19 68 93 150 310 378 11 32 33 403 332 419 158 205 273 364 36 136 346 369 327 367 339 423 129 422 67 267 43 175 87 150 233 382 40 364 224 412 55 297 90 129 5 350 64 257 322 372 97 345 239 245 185 358 15 256 1 252 245 350 100 344 58 74 230 276 256 288 91 133 148 237 73 249 340 381 160 278 30 153 245 335 …
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 <= 3033; 0 <= m <= 3033.

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