CT47922

The Whispering bridges of Asha

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Asha runs the mint at the beacon hill of Lantern Tor. Today the books show a list of bridges, and the numbers must be worked out before sundown. 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 <= 1508; 0 <= m <= 1508.

Example 1:

Input: 488 135 118 156 54 131 286 448 125 357 86 200 144 479 107 358 205 220 32 377 182 421 320 351 111 302 279 298 91 483 390 414 79 285 11 307 133 452 152 359 319 456 8 486 462 479 95 156 20 427 443 484 16 479 298 306 67 376 313 476 265 295 4 202 95 479 25 173 23 238 107 117 335 470 195 317 102 345 117 220 251 381 209 293 78 216 57 90 396 405 146 372 21 413 177 355 151 307 59 118 139 468 47 136 303 468 84 199 30 237 119 420 268 331 10 412 177 267 394 457 101 376 374 413 69 404 271 397 111 236 324 458 284 286 23 355 143 173 450 454 18 80 34 172 197 247 56 185 95 315 234 243 61 121 115 406 355 483 136 300 230 449 354 434 232 277 97 252 77 364 80 316 102 389 306 375 99 179 159 430 16 223 403 418 126 140 320 347 340 458 94 102 148 267 86 294 176 320 198 440 161 308 70 415 339 462 88 401 104 299 7 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 216 217 218 219 220 221 222 223 224 225 226 227 …

Example 2:

Input: 659 343 187 298 257 441 79 140 142 421 130 236 292 348 433 521 280 554 210 369 139 623 342 558 204 596 403 496 388 428 186 505 132 653 153 277 401 593 245 274 425 625 182 341 57 379 62 421 311 650 125 628 307 534 438 560 201 627 182 308 284 321 291 445 310 590 133 195 16 614 342 635 442 507 63 193 66 585 238 490 93 382 88 386 6 283 118 307 1 659 109 640 119 488 35 250 93 190 99 387 184 458 321 636 316 357 172 185 234 547 42 186 26 104 47 267 33 262 89 262 247 573 321 366 130 270 24 601 8 149 110 611 155 300 31 60 64 72 253 300 162 254 556 622 206 551 280 323 412 559 201 452 130 566 361 428 286 398 537 631 426 657 534 540 353 430 554 641 498 564 110 520 114 262 280 447 140 154 41 366 78 538 146 251 356 357 415 466 188 563 5 456 179 591 533 604 66 70 120 593 189 338 85 602 285 624 64 188 439…
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: 503 315 7 167 83 158 246 488 135 197 103 405 201 334 175 238 3 106 73 196 37 116 37 61 262 391 153 183 103 135 36 223 331 439 271 496 269 413 362 476 423 486 11 209 269 345 209 459 36 399 72 377 85 275 296 337 36 182 227 411 49 471 236 252 163 269 45 139 242 252 200 250 110 293 50 58 185 269 277 503 113 294 246 317 480 482 34 332 103 422 120 251 96 426 221 398 411 439 43 176 141 201 138 205 179 185 204 409 79 234 339 418 216 464 94 452 410 443 162 272 139 269 191 289 226 380 15 300 103 234 345 497 93 269 258 489 158 462 6 185 155 197 104 185 205 323 127 302 56 186 52 148 73 439 131 139 123 155 469 494 78 330 254 382 223 469 81 268 154 221 297 417 225 430 254 338 93 411 233 265 259 287 2 144 80 248 116 303 316 390 57 301 108 287 132 246 27 129 335 375 129 231 62 403 144 364 348 502 205 413 …
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 <= 1508; 0 <= m <= 1508.

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