CT46639

The Build Order of the Amber routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Trader inherited the archive at the wren hedges of Thimblewick along with its curious bookkeeping system for routes. Time to make sense of it. 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 <= 3002; 0 <= m <= 3002.

Example 1:

Input: 741 1280 418 680 628 673 63 283 330 606 308 470 117 320 160 248 218 299 302 664 577 699 346 484 81 383 45 524 649 720 376 391 555 593 253 360 477 536 135 189 42 476 280 427 183 196 169 694 125 685 56 603 627 715 158 232 226 655 237 319 369 705 410 600 266 309 265 311 273 681 75 550 153 585 171 674 164 491 121 497 543 717 246 547 234 343 213 655 154 254 282 478 266 538 315 567 670 738 554 563 148 387 493 739 158 276 42 269 20 216 186 436 150 502 66 408 115 658 245 288 244 692 376 436 573 576 86 247 61 740 631 672 76 386 523 651 191 522 344 576 65 108 144 606 282 511 387 633 18 115 358 385 242 685 26 667 256 399 66 669 340 546 240 501 401 646 25 433 201 639 4 311 96 353 466 699 248 534 39 324 261 511 20 49 435 659 38 633 512 542 582 703 530 617 29 686 113 490 427 661 416 614 300 604 203 386 …
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: 208 208 55 124 69 151 17 92 122 159 6 83 29 178 15 169 89 147 118 164 74 150 22 67 133 156 49 77 60 147 19 169 74 160 104 112 17 183 87 151 150 152 15 200 143 177 76 92 44 61 72 106 32 166 84 123 102 145 177 205 171 206 123 154 139 198 31 118 145 186 106 137 5 63 60 130 46 103 44 185 29 56 33 148 26 191 52 105 44 115 165 187 63 132 112 197 19 110 9 81 27 192 99 170 24 63 169 189 30 105 138 169 58 178 118 124 59 202 92 129 36 100 16 146 43 93 126 142 20 25 70 104 30 71 205 208 14 19 23 134 114 148 8 128 154 175 40 188 139 161 98 205 29 68 136 153 37 193 23 78 91 207 26 198 159 168 128 142 132 143 91 95 35 189 1 25 48 146 46 151 152 192 32 120 93 140 168 203 12 61 63 105 116 149 164 173 167 175 60 110 40 51 42 199 1 160 167 181 106 174 61 144 139 200 127 168 37 208 150 182 92 170 7 189 48 18…
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

Example 3:

Input: 2085 1170 115 1369 183 645 229 695 836 1537 203 1507 726 1164 514 1691 737 1954 788 1172 679 1737 983 1325 466 878 1606 1901 1179 1230 44 595 1061 1993 1130 1799 384 799 1284 1575 264 1540 1053 1664 1301 1824 269 1951 18 847 642 1031 319 1115 1004 1206 218 221 53 438 909 1193 240 702 524 1996 841 1549 144 1600 416 1930 899 1287 292 851 834 1339 499 1159 928 2041 509 1922 1209 1580 1783 1853 712 794 528 1039 344 1432 18 390 208 675 1391 1990 681 809 1124 1137 793 1080 933 1061 423 1916 899 1790 690 1583 717 850 722 995 245 1628 1759 1811 713 777 645 1927 53 473 356 1370 1694 1958 300 1019 1257 1905 288 1390 659 738 352 745 1112 1302 608 1402 600 1235 1657 2055 909 1963 1309 1594 617 2002 1235 2001 1107 1541 608 886 1148 1730 459 1333 848 1747 709 1412 62 978 541 1641 712 1749 1558 1629 166 …
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 <= 3002; 0 <= m <= 3002.

Loading...
Test Cases:No test cases
No test cases available.