CT57754

The roads at Redrock

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the canyon post of Redrock, Qadir records each roads in a worn leather ledger. The guild wants answers, not guesses. 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 <= 1069; 0 <= m <= 1069.

Example 1:

Input: 315 121 172 267 31 204 56 251 87 257 143 248 190 296 11 16 212 315 88 216 201 229 291 312 188 194 136 243 162 182 129 156 109 157 52 266 125 310 84 193 33 100 140 263 69 91 74 123 66 279 94 166 183 255 27 65 283 308 76 280 77 145 24 59 49 73 216 223 16 175 164 288 169 174 56 180 153 307 163 287 157 246 235 261 54 154 134 191 55 211 23 284 91 299 105 251 56 199 239 307 258 269 45 224 175 232 101 178 66 249 125 293 42 263 25 132 175 314 141 295 201 315 196 290 110 128 153 204 279 291 15 237 39 48 91 314 54 295 104 147 40 183 73 97 33 246 150 235 113 117 16 206 46 250 209 288 52 64 90 138 225 266 55 263 15 258 13 188 16 302 100 207 21 110 69 289 179 293 97 180 141 160 103 143 55 287 67 174 38 296 77 94 74 310 155 290 72 115 81 259 236 267 75 209 37 211 86 251 244 315 75 122 82 229 213 293 140…
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: 687 145 407 604 5 503 445 497 180 253 61 191 159 415 167 525 71 552 250 634 22 437 142 551 453 649 42 111 81 451 33 299 493 499 102 112 103 632 188 459 409 476 233 456 519 650 647 664 385 471 294 345 318 574 75 300 155 629 78 125 465 595 346 453 476 590 105 176 64 569 141 557 13 14 421 524 371 543 164 336 376 408 312 321 184 327 118 252 182 604 553 560 195 613 38 75 260 493 17 77 449 640 514 687 148 573 71 211 43 557 196 610 53 121 133 304 612 672 159 309 13 327 265 413 61 615 19 402 201 649 146 492 204 397 64 369 487 512 98 373 267 491 253 408 198 417 182 680 145 339 169 678 472 483 408 610 7 175 53 113 21 273 23 371 82 340 367 507 332 390 93 258 185 437 380 583 304 407 84 277 60 371 275 445 112 525 50 316 304 553 294 526 25 134 339 356 349 672 571 596 166 653 183 604 138 623 141 556 454 …
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: 545 680 55 384 145 231 197 497 119 333 88 160 200 464 154 484 325 486 217 233 314 463 232 426 176 394 272 497 110 175 128 540 98 278 298 324 253 468 400 514 120 255 1 37 121 198 39 212 318 412 216 444 369 437 283 460 132 263 87 101 331 428 59 285 241 299 4 397 42 162 207 373 25 518 159 348 168 377 39 161 1 312 488 522 58 197 303 544 87 316 467 527 235 525 276 438 29 398 143 544 259 450 13 206 92 315 343 454 269 279 272 448 296 369 199 464 33 69 19 135 320 353 100 215 314 335 320 402 239 255 135 202 85 391 34 331 181 444 53 333 79 302 24 228 382 386 227 480 484 528 325 357 46 369 25 210 212 214 278 453 112 542 20 165 1 63 45 274 266 527 41 493 203 268 23 526 4 38 88 91 138 158 160 307 22 349 54 531 219 308 66 100 136 490 168 413 233 403 112 521 214 258 3 310 106 422 141 430 96 150 67 385 21…
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 <= 1069; 0 <= m <= 1069.

Loading...
Test Cases:No test cases
No test cases available.
The roads at Redrock - MEDIUM Coding Problem | CodeTikki