CT46880

Bram's corridors Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Bram found an old ledger of corridors in the exchange attic at the mangrove channels of Rootwater. The margin notes pose a precise question. 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 <= 3108; 0 <= m <= 3108.

Example 1:

Input: 476 1598 176 386 102 351 7 429 181 281 20 30 201 407 8 236 39 271 137 392 276 303 6 214 82 249 160 398 97 297 273 454 195 392 225 452 182 235 252 371 118 280 176 393 35 189 87 111 18 158 63 64 464 465 276 377 146 347 51 256 271 452 156 215 45 383 79 196 367 435 67 445 217 289 76 328 144 433 62 301 18 140 11 148 47 48 8 474 157 271 259 355 384 387 337 396 21 157 60 304 195 264 137 372 25 47 229 337 45 86 180 468 9 437 302 407 59 307 214 265 379 383 374 378 26 187 225 390 404 410 57 201 20 475 171 441 77 256 214 240 8 136 173 458 234 461 8 113 9 340 108 436 246 415 254 342 326 376 71 172 198 353 124 448 63 473 223 264 46 416 60 255 98 114 424 470 123 363 56 282 315 378 67 222 204 327 379 394 318 351 83 273 189 200 258 398 261 311 341 418 177 416 117 191 275 472 414 428 17 386 202 455 399 450…
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: 769 2651 275 665 21 85 264 335 249 659 373 421 241 275 441 549 238 478 281 375 119 419 86 364 266 306 42 546 108 684 78 125 295 392 235 240 88 571 420 731 61 231 88 612 278 382 130 309 352 621 20 173 330 385 145 309 346 721 309 512 226 497 307 713 504 638 18 617 180 373 153 265 667 744 333 672 429 506 549 760 244 408 153 540 590 702 275 390 119 503 266 406 326 517 222 314 290 727 586 652 146 216 497 666 322 351 660 668 149 210 57 452 593 688 19 742 476 539 762 766 51 433 205 644 471 473 425 697 24 500 460 635 82 658 462 551 48 562 609 638 238 599 75 490 291 589 358 596 24 297 254 273 351 386 41 75 136 416 332 360 302 579 7 362 161 423 656 743 461 647 301 390 120 645 114 201 102 393 199 611 296 702 54 532 157 756 161 503 72 620 147 515 145 490 158 470 19 519 115 147 286 530 260 551 108 203 …
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: 176 3015 112 123 48 108 25 133 27 159 25 94 103 107 64 98 53 162 88 108 24 85 145 162 7 109 52 100 7 19 32 45 100 123 9 37 55 164 27 133 77 155 10 114 52 80 66 120 69 157 50 155 38 106 37 64 16 90 5 54 43 95 1 53 50 112 69 86 128 140 150 159 31 83 34 95 52 163 114 144 154 169 34 113 79 167 41 129 57 171 44 46 68 126 26 175 71 83 101 164 2 25 48 150 32 65 110 123 25 36 127 130 46 79 40 45 113 133 87 141 7 102 78 113 28 90 94 168 104 136 52 152 10 21 21 83 27 170 54 73 160 172 91 176 77 103 54 174 11 40 23 117 21 94 12 167 47 141 147 156 18 76 1 52 13 60 111 112 117 141 2 11 71 166 11 88 60 167 59 140 18 21 4 102 70 87 94 163 144 161 114 142 28 66 46 60 6 55 48 95 22 100 15 123 49 173 8 38 62 136 3 164 59 64 32 59 69 169 74 111 38 146 46 51 134 151 99 100 65 131 26 61 45 166 121 135 72 141 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 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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Bram's corridors Reckoning - MEDIUM Coding Problem | CodeTikki