CT36629

Esha and the Secret tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the pearl fisheries of Nacre Bay; Esha weighs the day's tunnels manifests and starts the calculations. 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 <= 1102; 0 <= m <= 1102.

Example 1:

Input: 489 272 403 428 217 313 259 310 314 388 259 326 165 194 110 121 94 401 129 416 232 456 405 444 62 438 173 364 122 351 214 276 265 326 142 307 381 459 280 410 204 381 249 290 43 109 72 327 124 427 160 314 301 450 64 327 190 267 119 197 87 324 303 352 408 457 51 480 23 251 269 277 142 337 338 448 41 87 1 38 285 405 309 408 288 351 87 461 173 216 130 170 14 119 62 366 141 398 18 198 184 397 4 472 108 175 264 422 269 395 76 445 18 372 164 268 64 237 150 202 335 422 73 236 199 423 332 375 228 366 89 223 248 408 110 297 132 277 27 318 257 294 185 363 182 444 355 421 43 362 217 403 157 227 331 335 385 447 372 434 138 181 340 477 148 181 95 418 61 239 89 338 292 342 378 379 19 66 311 421 229 332 140 365 210 301 92 431 285 415 45 80 40 73 179 453 234 299 12 294 237 364 285 306 39 69 26 158 183 356 …
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: 484 598 74 87 404 417 282 373 325 472 421 451 175 320 74 118 202 205 81 112 165 479 46 102 100 310 95 146 169 390 283 375 193 384 62 374 201 456 47 155 116 386 205 383 327 458 12 79 178 346 7 142 37 101 251 387 50 137 210 458 126 292 270 430 104 227 326 379 314 355 111 210 141 464 74 209 4 26 7 171 110 330 39 299 150 279 58 125 139 155 4 111 189 397 305 435 40 56 124 170 64 137 341 455 309 351 195 280 205 320 160 448 221 295 274 332 28 357 71 318 45 133 276 282 228 279 109 369 190 303 107 373 351 362 74 306 371 446 53 297 95 358 263 471 25 55 235 467 391 483 40 131 198 309 225 376 101 212 230 420 194 418 147 150 190 269 363 448 3 142 229 244 161 308 61 276 6 77 87 458 82 435 186 295 12 23 46 381 156 471 96 392 214 462 233 294 83 415 34 168 1 54 242 283 237 358 192 419 352 426 147 475 134 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: 52 296 33 40 33 52 9 47 10 33 6 18 6 10 1 52 4 14 17 34 10 52 28 43 24 46 14 52 26 51 17 27 13 14 6 24 18 29 8 15 16 37 7 16 20 39 12 52 8 31 49 50 31 51 6 35 1 27 45 46 11 31 5 41 21 33 33 50 13 23 22 35 15 34 3 11 13 45 33 48 2 49 9 50 38 49 22 37 28 32 2 10 1 36 8 20 8 35 24 29 5 28 39 40 1 10 17 38 2 34 19 52 25 32 15 20 19 21 9 26 22 26 6 45 22 38 9 52 8 12 19 25 3 50 10 21 15 48 36 42 7 35 18 34 8 39 44 47 6 39 8 24 4 39 27 37 3 19 25 50 19 35 2 46 30 35 9 43 1 46 14 21 31 32 39 50 20 33 39 51 4 5 2 36 11 44 9 40 34 48 16 46 8 40 39 42 35 43 16 47 18 32 7 19 4 20 12 47 30 43 28 41 24 50 18 23 40 45 3 44 17 40 12 33 5 22 27 28 37 51 30 41 17 36 14 39 21 46 11 24 6 25 4 49 30 52 22 44 1 26 19 44 11 47 5 35 29 39 45 51 23 43 8 44 20 26 31 33 5 48 42 46 16 50 3 20 17 48 24 49 8 51 10 11 …
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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Esha and the Secret tunnels - MEDIUM Coding Problem | CodeTikki