CT51139

Boris's Lazy tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the port of Emberfall opens only for a perfect tally of tunnels. Boris 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 <= 1293; 0 <= m <= 1293.

Example 1:

Input: 529 1042 443 452 259 482 211 475 78 138 40 396 12 295 17 278 187 324 65 313 269 489 464 523 171 463 56 298 178 334 89 331 209 357 13 235 230 366 157 297 342 497 195 436 213 479 43 339 397 505 441 469 25 325 186 376 238 267 87 468 292 440 187 293 323 424 210 306 313 354 14 315 237 373 253 503 502 507 353 437 88 299 294 398 221 285 374 395 416 421 53 476 281 469 214 441 132 375 74 346 293 341 65 405 301 437 9 344 65 136 101 436 23 506 322 443 409 524 62 324 256 350 47 215 11 383 25 488 164 516 154 222 301 315 268 474 57 244 36 137 125 255 235 323 51 116 149 253 28 432 201 492 72 113 129 274 124 189 109 509 16 350 191 239 144 270 11 365 320 526 245 526 10 111 20 250 65 476 330 485 4 448 154 202 111 466 287 415 257 353 55 147 276 323 334 345 25 138 167 424 49 164 207 497 17 398 220 284 142 369…
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: 657 43 174 561 232 265 125 402 270 381 452 520 69 409 87 589 26 537 182 325 151 586 109 543 302 646 510 616 371 480 32 74 74 561 103 561 284 424 266 550 352 422 51 166 4 460 61 328 370 390 404 456 441 636 193 616 537 652 297 631 361 549 489 586 282 611 210 379 414 568 623 656 65 340 48 392 56 435 419 589 238 252 271 548 364 559 378 562
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: 921 278 45 569 82 83 313 784 133 615 354 757 151 298 69 831 62 350 243 251 226 751 397 611 43 286 428 834 302 350 537 920 259 847 105 287 217 477 665 890 275 850 38 581 158 724 269 297 196 264 442 578 40 196 76 499 793 907 310 382 363 667 261 262 655 717 348 914 406 592 45 287 364 668 615 673 134 733 665 837 534 835 717 844 277 389 131 555 69 496 72 245 222 896 9 674 3 780 86 457 263 691 536 570 415 886 95 548 64 155 288 647 127 797 89 589 705 859 200 909 203 475 54 587 117 665 420 515 454 821 48 572 180 272 4 915 292 614 246 793 179 625 389 794 271 913 350 671 629 911 125 494 83 823 439 551 479 725 230 596 766 800 160 749 61 89 471 588 91 893 512 867 355 921 340 546 309 695 438 566 619 816 30 276 288 787 43 709 160 815 394 805 203 832 152 769 700 782 7 243 739 784 508 911 130 737 8 48 163…
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 <= 1293; 0 <= m <= 1293.

Loading...
Test Cases:No test cases
No test cases available.
Boris's Lazy tunnels - MEDIUM Coding Problem | CodeTikki