CT44213

Last canals of Clerk

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Clerk the customs officer watches over the coral atoll of Pearldeep's stores of canals. A careful computation stands between order and chaos. 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 <= 1565; 0 <= m <= 1565.

Example 1:

Input: 1553 732 1265 1501 238 451 1132 1152 630 659 726 1273 10 1350 887 1014 487 1077 550 1181 1044 1273 129 649 1172 1368 410 1526 1303 1473 480 982 343 667 125 774 926 1264 978 1078 483 1426 1051 1253 1000 1269 1248 1374 290 1134 802 1398 933 1123 1317 1365 1007 1181 17 612 734 1196 196 676 171 946 81 670 791 1143 1035 1069 148 1016 603 1374 1338 1398 64 1121 56 767 147 813 532 548 604 1116 85 1120 47 1059 222 683 1017 1141 94 1219 647 1491 1235 1285 964 1177 1133 1231 170 429 666 821 161 1205 1366 1465 596 803 812 1406 539 826 181 1380 918 1373 943 1460 1089 1510 312 797 1080 1352 114 613 58 1541 652 697 886 1359 216 989 1303 1400 1464 1520 96 1356 647 878 628 730 723 914 1109 1459 1067 1143 1072 1466 202 865 1151 1268 842 1362 389 604 906 1486 870 1383 427 1227 102 608 1033 1139 995 1244 283…
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: 22 231 9 15 2 8 7 12 5 16 16 18 17 19 7 14 3 9 4 18 8 13 2 10 14 19 2 15 3 19 4 10 4 6 19 22 6 17 5 22 3 18 10 18 11 13 12 13 3 13 6 13 8 12 7 19 11 18 1 16 1 6 1 2 17 22 9 16 9 14 6 22 8 20 4 21 8 17 1 15 14 20 10 11 7 15 13 19 7 11 11 19 18 21 7 17 4 15 10 13 17 20 12 22 2 3 7 10 7 9 14 21 13 22 5 17 4 17 8 16 4 20 1 4 4 22 1 18 6 16 13 17 15 22 2 4 12 19 6 9 13 16 9 17 3 15 20 21 5 13 8 11 3 5 9 18 14 16 8 21 7 21 10 12 1 9 10 17 12 20 10 16 1 5 1 10 12 18 4 13 4 7 15 16 9 10 5 6 5 9 9 12 5 18 8 22 3 21 16 17 2 19 8 18 4 5 2 12 18 19 3 14 4 12 7 16 5 7 10 15 1 19 20 22 8 14 1 3 12 21 6 21 5 15 13 18 3 20 7 13 6 19 2 6 10 20 6 7 9 20 1 14 1 17 1 12 4 8 7 20 15 19 5 14 3 11 2 9 9 19 4 9 3 22 19 21 5 21 14 17 10 21 5 10 11 17 9 11 2 22 5 20 2 20 15 18 6 8 12 17 3 8 1 22 4 14 10 14 6 10 6 1…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Example 3:

Input: 267 742 98 141 174 178 134 180 17 205 31 37 177 265 130 187 226 228 100 154 66 156 49 138 42 227 68 222 2 64 166 208 32 253 27 156 25 52 69 197 3 256 148 265 155 265 27 56 162 185 127 159 2 203 60 130 137 210 95 202 149 232 169 207 73 106 4 53 24 138 25 51 163 254 73 169 65 239 59 93 50 92 1 55 109 225 36 196 112 161 96 238 178 259 76 88 7 109 46 69 109 222 214 259 120 257 2 159 101 238 237 247 187 220 126 132 170 232 54 126 1 159 95 238 84 109 237 263 32 57 178 264 79 255 86 258 242 259 161 212 134 163 29 189 98 172 19 226 61 236 14 136 90 182 5 181 43 241 101 145 86 196 69 88 197 243 122 139 146 194 47 139 50 153 67 189 61 194 13 38 69 173 96 225 30 100 87 195 19 117 147 232 229 266 105 149 4 111 75 110 59 246 114 190 39 203 44 222 172 243 189 214 63 202 64 266 33 178 195 198 26 57 10 15…
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 <= 1565; 0 <= m <= 1565.

Loading...
Test Cases:No test cases
No test cases available.
Last canals of Clerk - MEDIUM Coding Problem | CodeTikki