CT60485

Ancient canals Build Order

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The chronicler Quin has been asked to reconcile two mismatched ledgers. On the desk lies a long table of canals 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 <= 2988; 0 <= m <= 2988.

Example 1:

Input: 1418 2312 180 344 378 801 860 1270 437 852 325 634 525 1235 405 436 15 671 464 587 439 1013 531 968 119 186 686 1110 710 1019 927 1012 122 1025 759 1357 157 584 533 1033 1129 1276 313 516 796 1226 994 1313 87 103 439 1418 325 1134 1167 1388 1019 1335 676 810 712 916 489 1063 1014 1117 751 1107 743 749 624 977 140 752 277 1241 187 1081 466 1266 469 993 180 713 984 1327 241 943 744 1078 438 493 511 1320 608 1379 440 497 47 505 494 1215 526 682 753 938 200 1265 700 1086 645 771 87 592 64 972 44 561 1226 1254 1149 1409 143 1120 403 999 316 559 712 816 300 654 192 1091 1005 1079 178 852 957 1117 327 1284 617 1177 285 367 51 816 560 869 216 580 361 677 864 1336 762 903 649 894 1061 1409 95 1025 265 456 1143 1287 856 1312 74 965 160 1115 202 1011 267 577 64 1404 649 1375 33 511 262 1380 1099 1356…
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: 149 61 2 102 42 60 60 135 43 90 71 103 66 140 21 111 80 134 18 55 10 79 72 145 2 133 12 66 79 83 6 139 44 144 18 66 25 141 127 139 75 97 54 143 38 144 4 46 42 72 51 71 22 41 88 91 36 146 59 85 102 112 7 116 67 120 68 124 5 92 31 138 12 95 71 89 98 135 7 130 86 132 68 121 101 137 34 145 19 133 17 37 76 133 1 26 83 133 36 37 23 85 75 84 67 84 28 53 9 138 94 128 29 94 43 125 33 39 4 13 37 54 141 143
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

Example 3:

Input: 1278 711 121 1122 819 988 278 525 80 1141 156 879 306 741 123 129 332 694 93 1064 1006 1136 653 972 70 367 409 517 309 1081 433 993 267 859 282 1247 435 605 1061 1209 136 551 445 562 697 850 373 553 383 798 15 767 953 1061 91 99 1057 1201 912 1269 70 1046 632 801 674 1171 87 567 260 961 286 1098 1008 1258 777 1007 221 889 202 1115 86 1034 151 1084 143 1032 824 1038 76 1082 3 1129 995 1268 234 596 557 1020 520 841 254 552 453 848 562 1225 983 1179 273 442 307 1168 418 928 814 1015 29 84 364 1010 136 849 144 1251 188 371 3 1051 251 572 73 797 463 681 669 737 121 784 55 808 8 885 507 670 223 1035 379 897 518 662 727 734 114 785 660 694 921 1174 168 794 645 894 47 711 377 404 585 1234 71 932 673 815 485 492 394 871 412 1209 285 845 28 160 229 862 291 1172 362 1108 60 692 385 675 190 796 344 47…
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 <= 2988; 0 <= m <= 2988.

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