CT54028

The Slitherwick Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The scribe Steward has been asked to plan the festival budget. On the desk lies a long table of bridges readings. 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 <= 3444; 0 <= m <= 3444.

Example 1:

Input: 1382 479 712 988 4 29 364 970 1068 1372 163 1266 984 1064 321 369 754 820 470 1316 186 744 885 1297 620 699 834 841 76 878 190 1092 253 714 137 1172 741 1143 252 974 19 1160 359 808 24 124 931 1269 495 1229 605 1136 295 1068 96 647 174 917 526 528 422 729 439 1213 395 484 990 1130 562 1043 324 572 1161 1203 523 828 408 724 292 1253 482 929 488 1321 305 708 482 1094 64 1163 1009 1081 344 1090 92 603 120 247 380 407 492 925 46 1033 148 923 1116 1132 761 1351 119 1312 727 1271 659 1003 1063 1111 419 1028 393 589 214 1139 662 984 24 93 437 954 233 345 426 1029 87 207 381 898 210 749 335 625 70 104 1211 1341 234 517 400 1086 474 1192 608 1308 46 1006 230 646 989 1368 1362 1376 230 402 694 754 363 821 145 862 577 601 1182 1248 1226 1356 597 1118 1165 1300 287 1255 147 375 339 962 666 992 472 493…
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: 444 929 60 212 1 322 256 368 22 359 184 340 9 276 207 437 107 402 114 360 213 422 84 203 430 431 59 95 201 378 142 342 115 375 178 329 223 308 63 382 105 434 274 327 29 325 79 391 208 409 264 304 17 247 139 239 326 335 12 86 46 395 48 434 28 235 77 346 123 403 174 353 183 197 408 436 55 100 91 329 271 366 95 293 158 435 327 411 5 430 72 371 35 261 165 382 29 268 89 418 330 383 119 153 168 276 214 319 161 444 164 371 10 277 385 421 253 332 43 70 67 82 72 384 135 333 163 426 92 186 11 228 188 371 186 346 19 37 53 200 150 444 1 93 158 425 131 300 41 217 304 327 120 122 174 361 30 55 5 86 311 335 226 338 208 284 19 60 92 315 111 433 180 329 307 354 103 175 24 392 88 244 391 419 26 302 263 432 273 438 126 442 153 330 19 226 169 242 306 433 185 248 228 385 118 289 84 252 109 154 210 440 101 219 …
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: 2764 3107 1078 2086 460 2105 1463 1547 1198 1784 369 1791 979 1365 890 1749 2165 2317 630 2714 1270 2162 1947 2380 1294 2436 1606 2738 162 663 1711 1994 2177 2447 902 1791 961 1500 1996 2215 138 1448 2342 2497 573 2027 2130 2688 631 1363 1011 1803 408 2582 277 904 826 887 576 831 1015 2060 990 1540 36 1204 767 969 464 1660 723 1108 535 2535 213 508 190 2567 296 2215 1129 2038 463 801 280 847 1372 2457 455 799 985 1298 669 2202 1054 2170 825 2121 633 2064 144 2424 2556 2716 2081 2635 1143 1265 41 1977 1936 2567 141 1272 325 1359 940 2169 1646 2217 1664 2296 453 1102 770 2407 1404 2517 507 2253 1552 1702 753 1073 938 1545 238 403 874 923 1649 1731 717 856 92 1141 203 496 2125 2658 1601 1796 1060 1074 1135 1917 911 1004 1048 2519 411 517 1099 2230 819 2093 1154 1947 592 1127 570 2470 1436 154…
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 <= 3444; 0 <= m <= 3444.

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