CT57408

Alaric Counts the routes

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the rookery of Crowhaven. Alaric spreads the routes records across the table and picks up a sharp pencil. 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 <= 2365; 0 <= m <= 2365.

Example 1:

Input: 477 1583 149 316 56 256 171 474 162 221 121 141 91 337 128 329 5 331 201 462 360 454 18 402 92 413 45 160 327 361 381 409 20 303 222 322 376 472 271 283 110 477 365 412 61 397 61 407 342 417 132 344 290 476 157 345 129 460 187 286 52 141 212 366 19 425 102 249 157 233 56 85 48 92 17 305 83 209 233 385 124 470 279 472 192 432 313 317 274 399 48 384 167 439 56 249 305 351 13 160 46 165 199 391 28 208 137 379 405 440 196 442 91 192 308 401 17 114 284 345 258 463 62 236 23 422 97 119 334 468 113 456 425 447 54 256 385 436 292 405 40 464 116 200 16 162 185 343 87 112 72 318 172 234 339 412 271 366 223 382 320 365 22 351 130 456 206 407 97 112 270 298 178 307 160 444 158 383 1 169 19 263 205 304 90 209 136 439 239 423 11 221 97 352 327 469 194 285 188 233 177 455 201 267 292 337 117 431 90 422 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 …

Example 2:

Input: 1429 367 291 1219 1210 1211 462 1091 563 763 1070 1301 387 444 478 1142 36 354 372 673 770 1314 718 763 693 1029 833 1134 756 1419 149 1364 480 661 765 795 916 995 128 644 902 1075 181 1079 528 1244 320 919 160 245 125 1155 231 1358 532 859 1042 1271 56 215 50 157 727 1423 442 1039 793 1058 1335 1404 1277 1294 394 461 435 1199 75 1187 583 981 765 1288 464 881 39 507 38 1411 372 879 423 1326 457 1405 801 861 831 1276 108 1280 49 655 463 869 616 944 1248 1365 98 1249 733 1187 685 1133 366 583 550 612 731 972 145 905 499 1080 672 1274 126 324 312 998 208 1349 11 617 15 48 829 874 138 314 1140 1318 389 1341 426 1356 122 865 5 38 532 1061 487 753 123 1419 432 656 1054 1398 703 1016 36 989 711 1183 1 743 12 632 181 735 158 541 420 878 359 1179 1065 1202 567 1388 806 849 354 862 1158 1172 485 129…
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: 33 528 1 31 10 13 12 30 10 21 30 32 1 22 23 29 26 31 13 32 5 31 7 20 7 27 20 31 9 11 13 21 7 23 2 7 10 12 29 33 27 31 1 24 6 21 15 33 5 30 14 26 21 31 18 20 14 18 1 18 3 31 14 31 3 8 25 26 15 16 8 14 15 27 8 29 11 20 12 28 3 33 8 32 23 32 20 23 6 20 32 33 4 22 6 33 5 11 10 11 22 27 7 8 17 29 4 15 9 13 14 27 6 25 11 33 17 24 16 32 19 27 19 28 6 31 8 22 10 17 3 29 29 32 5 13 4 6 18 33 24 29 12 26 15 32 17 22 6 32 27 33 9 16 7 15 9 14 1 16 7 17 11 16 21 25 9 27 11 31 15 23 5 19 22 32 16 30 4 23 13 28 4 28 3 4 13 16 7 25 14 17 11 17 8 12 7 18 16 20 2 4 5 27 29 30 3 28 18 27 5 18 8 23 10 22 26 28 19 32 28 29 11 22 11 13 3 18 11 29 5 16 13 25 13 27 14 24 15 19 14 20 5 32 1 27 26 29 5 9 28 33 12 17 2 21 9 28 2 20 17 21 19 25 7 9 26 32 10 19 1 20 10 30 2 16 5 23 3 15 9 12 14 22 11 23 17 28 19 21 1…
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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Alaric Counts the routes - MEDIUM Coding Problem | CodeTikki