CT47376

The tunnels at Sleekwater

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ulrica inherited the tannery at the otter slides of Sleekwater along with its curious bookkeeping system for tunnels. 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 <= 1937; 0 <= m <= 1937.

Example 1:

Input: 342 1044 32 245 11 108 69 285 196 260 3 92 22 272 18 55 96 316 124 272 67 129 284 308 233 321 30 279 62 246 81 114 128 186 132 146 25 243 159 317 67 309 129 310 58 339 162 276 82 248 170 188 72 116 1 56 200 278 211 302 102 144 20 136 300 341 15 150 161 307 261 264 197 331 5 204 72 227 96 334 215 236 77 157 164 187 73 319 106 173 224 304 161 301 16 117 148 218 187 340 83 307 241 252 40 191 293 311 32 54 49 248 253 322 92 112 289 315 11 20 208 270 205 238 51 212 114 211 198 304 126 183 65 265 134 284 90 131 314 331 207 216 25 247 22 299 103 147 244 291 24 280 118 224 84 273 51 209 64 115 34 122 185 333 282 305 5 308 218 329 53 186 11 124 69 124 65 315 230 300 5 329 133 329 312 342 9 217 78 263 307 312 217 240 53 66 2 14 176 235 112 326 87 173 238 301 194 334 51 181 1 234 18 176 10 74 62 292 …
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: 276 408 152 187 102 105 86 227 119 120 3 56 39 151 91 105 106 131 114 192 130 176 220 243 140 164 136 264 86 222 31 37 37 54 24 64 97 169 94 267 34 224 194 196 1 123 5 67 93 110 140 183 66 118 63 123 36 129 197 226 24 32 206 245 218 246 120 156 50 109 22 146 89 175 43 121 52 64 64 157 161 186 248 256 78 221 47 59 38 210 16 65 105 208 156 254 118 206 196 273 101 189 143 196 49 141 72 97 192 243 101 186 119 226 64 227 76 224 7 106 56 102 70 226 76 174 3 217 84 114 142 187 96 229 34 183 14 38 1 22 86 184 89 249 130 212 64 161 14 82 144 192 5 168 54 227 135 173 194 254 43 124 11 206 27 269 52 264 6 134 29 44 137 217 64 95 49 117 140 272 98 101 24 131 70 217 74 150 101 164 27 160 80 214 145 265 44 129 197 233 103 257 57 199 145 189 46 267 57 94 14 175 69 133 90 270 15 134 5 86 63 192 67 141 136…
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: 787 925 71 644 40 261 140 185 611 751 346 599 272 564 336 609 170 756 440 756 129 340 469 683 237 787 311 499 103 230 194 697 6 149 106 456 117 556 68 304 144 470 297 490 86 354 294 492 227 578 567 659 380 752 442 645 370 399 7 174 542 766 27 545 96 287 269 683 65 280 464 737 422 521 355 785 274 395 336 611 385 389 328 749 285 509 228 648 51 752 475 523 140 371 374 478 64 246 148 776 220 422 150 378 144 460 544 781 322 566 224 316 263 273 146 620 433 626 67 223 175 211 354 362 77 135 380 662 368 715 115 322 171 713 140 309 357 516 47 223 640 685 392 473 47 631 119 776 93 609 621 653 439 506 297 317 278 623 253 678 264 786 204 549 123 387 244 669 107 175 408 732 652 673 291 297 408 554 4 771 506 785 61 768 357 538 40 422 292 340 358 437 422 593 9 137 159 167 186 233 62 752 158 733 150 592 4…
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 <= 1937; 0 <= m <= 1937.

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