CT40731

Corwin's Ledger of routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the honey farms of Buzzwell, Corwin the auditor keeps careful count of the routes. Compute the guild dues owed, every figure matters. 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 <= 1056; 0 <= m <= 1056.

Example 1:

Input: 776 141 8 64 140 719 329 358 469 615 42 311 49 272 132 327 355 399 76 304 166 671 7 259 306 463 48 507 238 326 271 464 224 385 428 708 447 536 361 744 23 161 630 724 443 595 143 263 71 435 74 268 612 676 85 386 454 642 150 282 505 727 195 515 181 668 186 321 236 286 58 94 104 581 542 724 57 725 68 515 134 685 165 361 100 309 623 645 473 511 183 603 358 657 47 98 281 553 51 662 85 430 93 149 536 741 441 580 62 72 27 508 323 660 87 555 368 639 642 728 187 318 615 652 312 660 202 279 365 589 631 726 220 248 553 605 418 661 682 712 495 654 535 698 125 245 178 231 23 585 117 442 331 533 330 606 415 442 436 658 85 424 380 752 9 480 565 678 84 395 79 346 31 86 161 552 387 760 274 693 17 500 213 358 543 680 282 522 55 468 51 277 350 605 282 328 430 454 188 420 211 318 492 740 514 547 131 762 41 31…
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: 640 39 277 511 132 535 163 198 86 271 289 416 424 616 109 417 294 487 116 515 23 305 72 515 440 530 46 192 22 481 231 640 137 536 145 150 186 413 30 314 342 570 225 487 281 366 268 526 162 331 118 607 209 416 78 270 399 513 373 455 119 175 517 587 141 393 232 460 128 315 368 576 418 591 263 390 569 605 216 549
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: 215 1044 32 82 109 182 48 163 4 57 58 136 175 200 129 209 83 171 19 167 100 182 137 153 6 57 7 199 47 203 24 83 112 119 62 203 63 70 15 29 119 203 97 150 172 183 34 163 108 131 92 99 51 128 85 185 33 172 48 60 33 36 25 127 109 194 154 186 117 182 40 112 24 104 85 90 39 84 111 210 79 116 35 97 165 198 44 197 62 180 72 176 35 193 52 123 124 128 123 198 88 105 3 10 165 185 132 187 2 137 43 74 42 56 98 127 6 23 4 80 135 153 10 178 173 193 45 88 57 186 152 190 26 78 116 175 104 191 60 189 114 132 42 122 58 97 78 88 34 211 149 187 94 141 123 137 152 212 104 123 62 188 6 123 144 195 8 11 27 31 35 185 135 166 178 186 3 211 45 150 29 179 52 91 164 213 5 151 37 148 18 70 70 156 29 123 157 187 20 129 119 161 158 209 89 152 34 99 117 173 101 214 97 157 24 67 179 214 172 176 29 175 169 201 51 116 188 2…
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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Corwin's Ledger of routes - MEDIUM Coding Problem | CodeTikki