CT57337

Manav and the Build Order

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Manav found an old ledger of routes in the greenhouse attic at the tannery row of Leatherwick. The margin notes pose a precise question. 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 <= 2590; 0 <= m <= 2590.

Example 1:

Input: 485 1695 167 419 329 393 288 304 353 412 208 395 42 415 68 103 467 473 29 212 307 410 278 449 192 383 86 255 125 241 38 146 226 322 58 132 455 475 22 155 28 297 253 437 40 420 14 59 286 387 283 345 159 424 126 139 129 180 131 384 239 460 387 469 293 403 117 159 12 438 189 225 48 339 379 480 172 203 46 160 96 434 323 389 289 391 339 359 5 37 238 467 99 403 247 275 14 29 228 362 452 460 354 384 53 397 106 451 9 138 217 352 31 302 87 432 399 462 110 352 183 298 6 151 372 450 440 444 86 109 124 297 288 338 122 225 63 395 140 277 179 261 376 424 4 160 25 442 231 409 80 178 122 283 41 340 332 341 92 322 117 352 91 477 155 311 373 443 72 100 24 178 320 457 153 395 183 444 43 299 13 96 195 431 2 461 27 385 152 385 376 416 77 261 96 451 340 407 26 386 6 17 268 400 116 159 218 333 66 447 197 223 117…
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: 2189 1945 589 1351 1769 1772 657 1565 1227 1683 401 1316 214 1688 369 2189 438 1469 765 2015 1546 2091 557 1511 344 1160 546 647 517 790 190 1780 1608 2078 103 376 238 1984 210 1079 73 2189 435 654 1347 2173 42 1106 47 1561 1360 2021 1861 1927 222 663 1082 1525 964 1626 562 1320 108 624 1281 1530 1939 1942 788 1264 278 1291 899 1008 1313 1845 804 1086 465 1246 646 1094 632 1689 46 1355 95 935 1511 1661 1018 1258 132 1576 1415 1567 475 781 257 1526 608 839 1256 1335 1755 2021 720 1489 1009 1627 246 1674 273 304 1023 1265 54 688 492 2067 1207 1681 1217 1377 340 484 363 1319 305 655 24 1290 1295 1562 284 1075 473 1532 699 1337 814 1210 449 542 1154 1542 1875 2038 1237 1513 487 880 1698 1884 1009 1071 157 524 510 1621 582 1182 182 1205 1486 1756 7 1261 33 1752 1402 1510 607 1418 283 2120 399 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 3:

Input: 1279 809 807 1070 1125 1212 173 259 435 961 851 1202 749 1089 230 737 368 622 988 1046 63 1148 491 1202 287 573 276 279 299 574 878 1183 1072 1259 415 520 647 680 594 1143 587 759 72 471 801 897 753 792 64 1197 400 963 387 1253 153 688 491 500 700 1021 596 1188 994 1241 52 1253 547 1035 736 1262 495 1130 29 241 1038 1074 169 740 334 916 572 836 22 766 313 637 4 683 310 663 104 1076 258 996 1060 1240 136 434 247 645 1050 1122 807 943 666 921 579 608 899 1126 163 1235 9 1112 530 994 1106 1158 1074 1090 95 822 234 938 1104 1199 472 1199 143 1129 237 527 186 961 148 275 745 825 278 1080 381 567 315 621 119 1186 16 89 498 730 512 893 631 996 74 227 339 1250 294 429 397 709 180 1169 572 1221 836 837 105 923 474 1246 1125 1225 969 1151 107 459 609 1180 1011 1185 279 324 258 1217 73 382 277 854 40…
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 <= 2590; 0 <= m <= 2590.

Loading...
Test Cases:No test cases
No test cases available.
Manav and the Build Order - MEDIUM Coding Problem | CodeTikki