CT36263

The Build Order at Tidewater

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the coastal hub of Tidewater with crates of routes, and Rohan the clerk must account for every last one. 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 <= 2516; 0 <= m <= 2516.

Example 1:

Input: 1566 1273 74 984 630 1073 433 1249 467 657 389 898 892 1175 124 1499 921 937 289 954 340 1404 189 282 99 265 837 1155 409 670 244 1401 525 1151 497 732 889 1062 604 1557 603 951 210 1190 280 1224 108 1038 968 1541 891 1370 463 1225 256 1528 267 443 724 735 518 1451 554 868 754 880 310 894 153 623 871 896 655 1383 181 324 463 468 596 866 147 1059 1500 1542 476 508 449 566 611 1133 893 1550 323 1056 475 932 1134 1369 60 1194 1071 1431 1048 1501 164 340 383 1214 594 729 499 1324 385 911 173 1238 110 191 563 1027 1270 1554 340 349 64 574 521 1121 129 980 161 1150 294 1130 562 805 1135 1478 1395 1484 44 100 630 1241 660 806 72 927 630 788 207 425 58 735 503 1295 1384 1520 447 1468 1070 1470 733 907 805 1020 1037 1094 367 918 348 899 622 1176 270 381 643 1174 615 1247 907 1351 571 1117 245 1086 …
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: 1995 1408 79 434 629 1269 515 1425 452 1189 116 930 453 837 414 1542 902 1154 1432 1733 640 1421 1148 1448 791 1416 318 331 961 1360 342 1843 50 462 761 1409 1402 1548 1235 1497 1112 1331 206 342 418 1225 111 1805 1137 1615 37 263 1672 1791 495 1940 326 1898 1076 1369 1503 1848 24 1675 184 877 733 1002 561 1975 445 1736 14 381 216 1045 836 1064 1496 1519 824 1060 908 1232 93 217 822 1894 253 1082 1160 1275 779 1330 408 1261 434 1049 677 1875 1255 1615 930 1907 279 298 159 160 427 1662 86 1441 1539 1816 187 1115 693 1138 304 1110 1256 1472 1645 1861 927 1645 730 1693 502 1421 600 1184 134 1007 1195 1453 1198 1475 1628 1778 1082 1286 960 1162 887 1931 292 415 1237 1938 333 1836 1746 1768 131 462 290 1604 403 903 94 1116 840 1724 174 649 1395 1742 975 1669 533 1553 1444 1917 243 637 1181 1313…
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: 473 2117 24 172 138 371 349 400 141 182 178 190 35 190 75 429 13 31 222 268 237 272 319 422 22 280 366 405 240 462 297 327 55 445 83 295 88 188 152 231 1 190 32 373 1 341 244 438 377 395 258 439 316 369 132 178 34 70 444 462 21 434 86 213 60 443 3 382 189 237 258 286 264 288 62 240 15 99 80 107 112 115 11 110 26 369 59 274 95 227 69 82 313 404 116 334 279 340 346 396 48 131 87 94 56 189 224 413 113 378 120 431 388 458 29 257 250 368 20 203 2 322 99 313 414 426 276 467 96 398 97 182 287 292 251 371 13 293 142 242 121 266 92 149 157 359 123 402 94 251 198 424 55 144 86 170 373 460 324 462 16 215 168 425 65 89 95 103 143 438 287 349 141 297 24 422 298 320 19 237 71 461 20 319 142 195 207 294 204 233 218 351 5 469 436 449 166 349 35 453 356 372 49 351 38 218 98 381 299 336 67 102 247 434 301 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 …

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Build Order at Tidewater - MEDIUM Coding Problem | CodeTikki