CT62096

Petr and the Starlit corridors

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Petr inherited the workshop at the glass towers of Prismhaven along with its curious bookkeeping system for corridors. Time to make sense of it. 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 <= 1156; 0 <= m <= 1156.

Example 1:

Input: 260 53 20 25 129 144 136 154 70 240 7 150 43 182 70 260 36 46 55 74 140 243 90 259 81 167 100 130 167 232 128 241 205 258 175 216 66 87 49 89 89 118 181 225 86 186 150 190 27 227 84 108 14 162 117 251 170 241 109 118 69 98 50 70 222 260 47 259 101 212 16 160 92 175 21 164 68 156 5 197 44 45 36 257 46 129 111 251 21 141 16 29 34 77 190 224 115 195 34 61 72 250 83 191 75 138 132 197
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: 859 564 501 551 230 510 205 591 396 755 26 288 421 531 246 550 92 503 541 658 266 320 178 846 44 323 185 701 613 696 474 574 75 604 130 217 628 634 634 677 118 204 222 264 312 521 542 657 70 485 541 803 810 829 562 664 189 652 507 551 202 762 330 803 201 805 609 710 160 223 147 605 258 367 228 418 19 515 613 654 68 524 763 807 42 846 1 234 224 661 274 318 112 157 256 357 395 674 73 708 367 835 284 359 352 418 24 768 74 816 72 628 80 465 587 733 306 642 34 843 385 857 363 639 67 360 351 523 403 618 294 807 484 513 63 149 1 814 291 669 699 814 493 755 485 631 183 285 177 739 4 478 283 510 79 102 57 341 243 513 33 819 11 188 72 796 128 370 213 349 263 305 70 842 250 268 592 697 772 791 450 833 63 373 192 344 34 818 538 559 534 822 2 537 472 750 525 550 35 478 403 686 145 764 317 697 126 620 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: 81 775 39 49 32 59 2 63 3 4 45 61 8 78 29 53 38 66 56 65 53 57 46 60 40 81 7 81 6 70 9 56 57 74 14 50 3 52 48 55 9 49 69 72 12 42 52 67 8 39 42 61 42 45 4 25 40 55 9 30 9 13 69 71 55 60 40 78 53 78 12 41 29 80 12 20 7 20 23 64 50 59 8 80 16 62 34 58 9 40 6 32 3 14 48 60 44 62 17 39 13 44 77 78 27 69 13 15 78 80 36 63 9 59 7 9 51 76 25 48 2 31 64 77 12 46 44 77 41 67 62 76 18 40 56 71 27 79 35 37 38 81 48 69 46 77 18 51 44 75 32 60 7 70 49 70 16 40 38 67 38 60 12 29 9 17 22 34 19 26 48 63 27 40 10 73 57 72 4 74 63 72 11 67 29 36 22 46 17 28 19 77 27 33 17 76 11 23 48 57 10 69 13 40 22 49 9 24 66 77 6 56 13 18 52 80 2 39 39 50 6 65 25 27 52 66 50 66 21 72 46 56 15 38 45 63 33 50 25 30 43 71 47 56 40 56 22 29 22 78 29 30 27 41 5 67 28 65 20 44 3 65 41 42 43 68 40 66 25 81 19 74 6 78 42 68 51 …
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

Constraints:

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

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