CT60393

Marek's Ledger of tunnels

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the clockwork quarter of Gearford opens only for a perfect tally of tunnels. Marek 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 <= 1036; 0 <= m <= 1036.

Example 1:

Input: 643 8 314 327 104 181 14 410 297 600 325 475 308 562 115 482 306 460
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: 340 650 263 324 28 134 50 121 14 259 230 248 36 51 37 213 173 316 284 306 182 245 153 304 87 194 161 162 11 259 127 324 165 318 119 178 196 250 8 191 206 328 14 330 155 164 269 331 3 251 64 323 180 228 212 340 157 220 217 302 10 274 89 155 40 236 77 288 65 290 210 323 117 182 38 179 143 179 106 201 138 200 103 235 112 204 250 317 64 322 57 299 60 133 40 221 274 292 115 283 101 246 90 323 192 196 28 325 244 281 53 69 122 282 180 190 119 193 115 284 117 275 317 339 33 301 74 149 49 61 249 300 73 332 27 138 168 282 66 147 22 303 61 107 80 112 26 77 231 314 85 181 13 14 33 41 122 248 130 322 158 261 134 253 218 264 218 283 87 152 7 67 233 305 140 158 51 216 146 308 57 165 106 259 96 191 65 178 219 221 171 272 73 117 125 148 211 289 166 324 14 243 235 321 73 191 185 220 123 214 16 148 49 149 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 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: 696 927 5 71 275 671 306 636 470 564 344 591 37 672 80 185 90 642 186 597 391 457 358 568 222 233 263 381 303 574 168 581 158 295 281 511 271 605 151 408 305 575 391 412 12 265 45 125 499 567 570 622 82 327 107 109 159 452 53 554 51 64 69 675 156 244 294 389 456 471 619 659 48 204 218 246 432 653 136 422 97 682 514 634 349 514 159 326 92 210 271 485 207 602 91 673 302 688 165 186 597 609 494 568 176 416 316 556 341 353 423 495 168 231 274 276 127 677 30 167 300 459 63 533 77 157 457 646 31 571 7 494 391 416 179 462 10 30 347 671 10 634 307 557 429 625 80 318 385 588 168 653 292 484 231 569 13 158 42 380 262 565 62 356 583 599 253 469 383 511 462 469 76 192 123 696 123 506 492 548 137 396 543 678 238 239 149 438 43 170 343 349 171 492 245 389 13 343 166 273 220 669 71 333 8 309 295 608 228 …
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 <= 1036; 0 <= m <= 1036.

Loading...
Test Cases:No test cases
No test cases available.