CT62237

The routes at Redrock

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the canyon post of Redrock opens only for a perfect tally of routes. Pia 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 <= 1642; 0 <= m <= 1642.

Example 1:

Input: 173 608 48 104 63 131 57 111 5 162 30 66 25 132 99 110 31 48 90 98 116 143 6 24 84 128 131 169 111 133 57 109 113 117 148 149 123 169 44 160 34 64 50 164 21 78 28 48 56 133 7 159 39 88 2 162 120 140 27 40 12 142 7 13 121 154 27 30 105 132 153 160 53 147 12 64 89 100 93 153 90 122 77 102 91 171 78 132 100 119 68 127 42 43 66 71 87 110 130 161 10 70 61 96 53 54 54 68 62 117 8 93 87 157 57 119 63 64 28 165 116 152 91 99 119 121 6 104 39 78 67 108 41 167 149 154 61 114 21 99 68 155 6 141 1 9 123 141 41 62 91 125 102 142 67 125 28 93 43 115 3 66 33 76 52 156 55 61 3 101 60 73 19 75 136 173 62 118 26 92 69 142 56 100 91 124 135 166 74 166 39 59 31 142 56 79 46 160 61 113 77 141 35 78 151 167 104 106 83 108 24 102 49 148 107 113 137 161 86 167 1 143 87 106 11 101 75 129 81 95 52 107 27 44 65 96 3…
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

Example 2:

Input: 662 1524 260 391 54 617 461 513 173 368 393 478 204 215 332 366 153 449 234 567 45 427 168 303 216 497 9 63 82 91 377 504 70 110 148 178 162 533 60 68 238 596 128 454 115 521 241 404 144 657 70 250 62 509 290 324 496 662 172 233 221 237 311 523 26 32 9 509 89 270 511 574 188 618 118 206 299 315 62 519 257 388 212 489 124 513 87 241 404 615 57 319 375 579 436 554 213 456 327 411 119 639 18 317 193 438 81 563 170 542 105 184 321 613 10 524 335 570 345 533 26 63 230 531 19 188 6 511 140 509 152 162 296 530 78 646 234 277 111 249 404 415 485 603 320 537 436 455 179 520 73 473 27 334 338 351 293 297 266 595 262 566 324 388 494 660 202 448 219 520 234 475 131 235 220 592 205 523 344 568 417 620 413 546 197 637 185 403 310 513 390 651 519 592 60 64 71 228 508 532 269 381 5 238 158 650 308 605 8 3…
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: 92 168 67 73 22 90 4 56 17 55 23 25 36 71 14 58 2 40 1 63 30 86 21 61 22 73 16 59 42 68 27 42 74 88 46 58 35 79 31 88 22 55 82 88 10 26 37 49 47 89 9 23 46 66 46 61 22 88 10 17 43 81 72 76 34 39 42 52 32 81 10 63 75 87 70 73 24 30 14 29 21 47 23 82 41 58 51 91 38 53 2 5 11 65 26 45 61 74 25 61 30 81 12 20 40 72 19 29 19 23 73 81 6 19 40 45 69 74 14 67 2 72 26 72 30 34 34 91 34 59 7 65 13 17 64 73 28 46 1 88 38 91 6 63 6 10 39 81 36 91 68 87 32 33 53 85 4 33 29 33 15 32 31 84 31 89 48 82 17 83 25 47 10 84 76 85 54 67 4 61 45 88 61 72 48 63 43 67 8 89 31 64 38 50 23 77 87 91 42 60 22 76 28 71 60 72 33 90 8 73 7 15 19 90 47 92 24 48 29 75 27 48 12 90 35 54 72 92 4 54 28 69 54 87 34 56 52 58 30 68 21 28 47 73 29 54 41 92 50 81 37 58 40 69 9 33 47 85 59 85 58 89 25 54 14 89 1 6 27 77 6 92 40 89…
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

Constraints:

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

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