CT46280

The Amberplain Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the savanna camp of Amberplain, Ivan the valuer keeps careful count of the routes. Approve the repair estimates, every figure matters. 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 <= 1746; 0 <= m <= 1746.

Example 1:

Input: 1447 1131 737 1070 1042 1267 468 761 190 1321 796 1179 503 1292 548 1300 44 319 1112 1408 40 1155 563 1019 978 1362 315 567 60 403 401 948 32 560 524 877 383 581 363 633 183 1025 493 955 635 1003 1246 1376 1107 1445 582 1174 406 1246 473 1381 513 735 1294 1299 391 896 898 903 373 1080 898 1211 448 889 103 286 1284 1390 1081 1352 6 553 217 698 175 626 758 1256 84 359 289 648 326 684 410 769 1287 1389 147 560 255 1237 636 1422 174 1176 523 930 655 1328 50 454 545 716 4 1221 722 1415 391 1280 397 1360 206 1045 492 1412 110 669 237 1271 593 658 237 284 494 687 559 721 155 879 912 1274 448 974 698 766 910 1183 381 528 1002 1172 615 929 250 276 892 1435 850 1285 633 921 189 364 459 684 1056 1321 791 987 66 780 34 1363 187 918 907 1010 672 1050 392 734 27 474 485 1164 783 1015 44 764 558 583 408 …
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: 1439 209 863 1231 1277 1436 126 537 433 1352 1273 1392 526 1001 321 1421 930 1219 195 1176 1042 1235 74 1055 5 496 604 608 847 958 1257 1260 447 472 1003 1140 703 1276 922 1081 180 793 745 1142 594 1295 459 736 841 1206 582 1297 371 942 375 1051 205 745 997 1309 513 832 68 434 515 958 404 530 287 1124 165 651 779 1418 1144 1310 237 1241 80 126 1057 1352 640 893 255 1287 983 1232 507 861 353 1121 39 353 290 582 640 777 909 1379 225 476 256 848 294 1084 265 528 1092 1305 833 877 514 570 402 1390 34 1300 93 972 366 854 877 1380 639 664 1009 1026 146 1194 395 743 1130 1392 163 224 286 794 237 1154 114 235 385 1062 283 1294 270 1376 465 1158 220 289 565 815 107 1086 823 956 121 573 797 1155 772 1152 709 929 316 886 459 1052 723 1218 477 1151 927 1400 5 407 437 1170 849 981 383 1367 1001 1036 57…
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: 231 16 171 197 34 120 50 112 4 29 66 219 1 183 64 72 2 159 36 147 19 102 89 101 193 218 30 145 154 210 44 135 107 211
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 <= 1746; 0 <= m <= 1746.

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