CT55496

Ranger's corridors Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ranger found an old ledger of corridors in the salt store attic at the ink district of Scriptoria. 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 <= 1089; 0 <= m <= 1089.

Example 1:

Input: 798 98 698 707 80 348 750 778 121 692 76 211 605 689 591 730 17 796 31 181 657 746 65 290 55 353 275 299 8 767 58 296 603 669 102 673 484 531 474 703 111 326 295 296 131 346 402 689 394 608 537 795 109 681 74 349 281 798 82 693 201 208 48 182 498 716 183 682 380 668 654 707 276 391 489 695 314 411 535 577 15 794 285 791 697 798 383 631 410 670 604 777 170 666 162 561 674 727 357 604 45 388 139 767 180 357 423 777 723 770 32 114 56 508 37 539 412 417 552 696 81 423 82 157 2 7 274 329 119 392 487 569 469 472 448 510 466 595 524 615 105 298 560 584 144 677 48 313 319 623 44 117 74 730 514 626 94 359 234 704 229 464 17 781 193 745 72 153 24 676 492 560 168 744 56 643 85 606 46 60 264 504 258 696 295 622 210 624 117 795 226 422 294 389 2 390 508 635
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: 609 301 14 465 130 205 202 312 138 231 129 442 5 527 86 393 384 606 304 326 386 437 266 604 117 452 341 553 344 573 180 187 248 339 297 358 393 507 147 349 92 98 541 562 9 172 294 478 120 600 83 220 303 511 131 381 212 462 33 146 298 337 130 384 151 580 92 146 8 347 179 606 49 139 17 531 450 460 418 591 251 319 519 542 290 470 196 590 488 552 162 297 138 536 2 322 151 573 347 491 42 584 229 489 283 527 107 480 144 299 167 212 90 239 15 483 73 300 187 245 122 527 135 320 145 232 361 509 173 518 461 511 212 328 154 535 92 564 179 470 208 479 150 288 199 435 70 73 87 135 479 539 181 234 4 161 253 427 254 294 45 214 342 565 276 566 59 395 139 250 129 270 41 478 292 479 184 254 475 546 361 574 83 518 56 65 205 496 361 419 101 419 384 494 144 300 77 463 281 525 195 321 390 548 472 567 38 167 116…
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: 78 236 26 35 33 37 30 66 3 65 15 76 42 50 3 34 53 54 11 17 45 66 13 17 10 28 10 60 13 41 34 75 25 50 21 34 66 71 43 78 21 76 33 68 10 36 7 69 30 77 3 44 48 60 11 67 32 46 7 43 44 47 3 36 21 44 18 29 21 71 7 60 41 42 61 76 24 64 46 76 42 60 51 73 15 29 18 44 62 78 8 12 65 73 11 49 9 63 15 23 34 55 12 68 34 38 11 43 17 75 11 66 17 25 25 58 5 14 19 34 39 77 44 46 28 58 9 11 15 21 7 34 22 61 42 76 4 73 6 24 61 64 29 74 24 66 50 56 3 37 19 55 21 51 15 55 46 61 42 59 29 64 2 7 48 62 10 40 16 17 35 57 54 68 59 64 34 57 15 68 45 49 9 55 54 65 11 35 17 33 6 66 21 52 28 46 3 30 18 22 26 46 13 44 39 62 27 54 19 59 14 45 44 59 47 54 77 78 6 31 15 37 55 59 39 52 38 61 34 36 45 71 41 56 8 41 1 64 40 58 18 36 70 74 5 45 8 42 4 38 6 76 28 45 36 63 3 9 18 49 47 78 9 14 2 66 24 48 30 32 44 69 11 15 36 53 24…
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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Ranger's corridors Build Order - MEDIUM Coding Problem | CodeTikki