CT44737

The Saprun Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the maple sugarbush of Saprun opens only for a perfect tally of bridges. Zoravar means to find out. 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 <= 2151; 0 <= m <= 2151.

Example 1:

Input: 522 975 361 417 4 267 149 290 5 400 288 459 240 362 231 472 235 382 188 276 65 457 269 318 215 344 197 498 76 392 168 278 172 479 322 351 306 392 154 497 48 444 9 184 109 197 192 386 68 507 31 402 282 502 390 455 117 262 98 154 313 352 147 222 18 374 59 490 16 443 383 464 169 404 97 146 78 102 76 288 67 374 275 481 132 374 353 434 99 520 57 369 83 514 75 465 226 373 309 359 293 329 67 123 306 386 311 369 54 115 76 347 196 220 5 46 168 240 245 336 443 453 175 471 44 152 389 390 123 317 9 407 143 471 239 268 93 299 19 285 2 439 106 118 33 359 330 497 253 350 15 399 31 165 108 210 243 503 216 242 197 513 30 496 378 451 192 256 267 368 335 358 70 507 27 90 254 513 106 450 340 368 46 164 149 431 299 439 196 446 150 203 68 497 247 401 158 363 115 448 393 431 105 456 254 436 151 418 220 251 308 4…
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: 282 600 24 149 209 244 228 263 72 276 19 226 227 249 47 121 93 144 33 280 47 76 245 276 128 217 23 220 111 121 158 166 62 196 73 111 99 149 95 189 22 231 19 205 142 186 123 138 149 275 205 261 126 135 141 276 56 259 182 265 115 261 4 211 166 175 138 228 179 236 66 81 14 99 93 253 185 195 153 271 86 276 59 172 83 137 98 241 120 134 136 250 65 161 54 67 17 222 236 267 91 254 75 191 32 231 107 114 167 239 35 64 17 82 58 221 28 260 72 103 67 188 148 258 135 261 138 211 51 166 182 201 104 114 178 230 62 220 28 206 179 210 37 102 112 211 65 218 76 176 125 166 51 180 90 126 25 231 101 228 39 142 47 65 210 242 111 274 155 193 5 69 69 226 72 139 159 240 4 9 45 102 84 188 169 184 84 99 14 69 186 273 63 86 62 140 63 93 1 120 31 56 18 108 186 215 64 189 14 245 150 240 58 108 10 198 25 31 15 125 123 23…
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: 845 394 122 508 583 716 28 187 356 460 199 652 824 843 27 768 326 510 234 452 433 526 381 808 345 624 341 520 520 587 176 778 297 461 758 782 623 708 608 763 160 804 338 399 76 125 178 566 54 529 153 652 137 257 110 354 104 116 371 421 268 557 691 760 54 779 322 356 456 715 197 396 29 226 350 395 276 747 224 688 345 822 227 236 338 781 232 353 60 550 390 822 92 644 322 394 141 165 376 806 314 756 707 788 162 565 523 631 366 625 534 564 469 491 473 534 463 601 517 740 168 479 108 767 210 372 241 762 8 299 391 686 151 441 173 756 650 691 375 657 215 344 619 795 594 642 255 601 47 521 444 573 374 665 27 432 53 831 394 450 381 671 92 575 223 418 342 407 122 646 136 235 30 664 414 494 292 458 745 810 603 698 797 835 287 764 23 117 489 789 266 454 119 805 258 630 506 683 2 20 36 805 412 765 205 …
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 <= 2151; 0 <= m <= 2151.

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