CT43147

Urmila's Ledger of canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the beacon hill of Lantern Tor, Urmila records each canals in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3315; 0 <= m <= 3315.

Example 1:

Input: 2902 58 2585 2674 2601 2713 581 2391 37 2295 2277 2360 977 2590 510 1282 2325 2755 1170 1199 1468 2826 574 2096 167 2594 750 1455 1206 1670 504 1782 2535 2846 179 2241 639 1951 666 2748 829 2751 199 1156 421 2797 1773 1820 14 69 179 1181 2447 2608 1213 2098 1734 2800 467 1507 165 1024 1510 2327 457 1603 839 1213 844 1893 908 2293 1125 2364 1162 2632 151 1101 1324 2755 829 2455 455 1762 913 1013 736 1879 214 1204 77 1150 1158 1356 2235 2396 179 2345 1189 2522 690 1697 1353 2380 285 286 412 2415 2374 2542 452 837 294 2690 1335 2483 1088 2834
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: 322 1769 104 109 2 269 12 187 70 216 289 294 143 312 123 249 23 314 151 161 41 289 38 94 177 202 122 316 115 124 37 115 269 313 98 179 94 253 26 181 78 128 50 88 162 263 54 216 9 238 105 305 13 110 134 272 64 163 28 100 78 201 41 283 245 310 123 259 119 271 28 261 7 154 242 280 103 231 100 267 198 296 114 233 167 262 125 251 170 267 254 257 170 233 19 279 7 107 45 308 22 98 206 231 35 260 84 94 132 272 123 287 9 285 73 282 9 188 2 268 152 313 30 38 67 138 92 271 4 295 87 270 181 308 93 99 201 238 141 279 116 158 74 79 179 250 8 312 81 115 29 112 69 100 127 188 234 322 78 298 30 106 93 215 206 249 243 290 67 167 14 241 22 298 78 99 238 287 164 322 86 288 232 240 75 252 120 236 10 104 198 204 197 244 54 270 116 257 110 135 30 92 87 178 176 272 32 315 197 213 20 207 114 187 54 168 160 203 186…
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: 192 1073 44 85 31 61 24 55 9 92 1 107 52 171 39 56 16 39 83 171 166 179 26 90 8 146 42 165 37 185 2 142 58 158 19 173 40 103 17 125 19 78 87 155 34 56 170 182 6 63 107 191 50 167 131 146 27 59 21 175 10 121 27 159 153 192 54 72 62 139 82 184 86 103 27 104 97 164 35 49 49 88 145 176 25 165 146 163 69 96 20 100 5 101 18 147 15 68 42 118 58 162 86 110 129 150 22 179 64 117 107 152 104 117 21 119 67 156 45 97 29 83 51 54 76 131 28 77 80 113 82 112 30 91 51 158 48 79 49 86 19 57 58 168 49 183 37 75 81 108 22 84 47 114 60 112 22 149 44 174 77 92 117 128 11 12 31 32 2 109 20 158 31 43 18 182 33 160 4 58 109 113 48 172 105 129 103 157 7 183 110 127 92 181 9 95 36 79 44 122 130 153 138 142 105 117 84 131 116 133 17 189 8 96 56 110 141 152 121 136 56 80 74 188 62 67 162 185 87 165 81 117 5 141 121 1…
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

Constraints:

1 <= n <= 3315; 0 <= m <= 3315.

Loading...
Test Cases:No test cases
No test cases available.
Urmila's Ledger of canals - MEDIUM Coding Problem | CodeTikki