CT58418

The Violet canals of Devi

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Devi inherited the dairy at the herring shoals of Silverfin along with its curious bookkeeping system for canals. 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 <= 1610; 0 <= m <= 1610.

Example 1:

Input: 196 1017 34 150 14 178 39 140 76 135 20 175 108 120 34 102 88 116 14 157 99 181 56 86 122 157 6 36 93 181 16 159 17 133 62 158 99 147 30 122 14 127 86 133 18 108 50 91 120 171 61 119 6 27 29 141 80 165 88 149 132 159 57 96 73 114 3 186 19 93 75 82 98 175 71 145 14 194 54 156 33 176 142 188 139 142 132 196 43 50 12 149 96 193 83 87 12 178 78 162 18 114 1 155 45 92 49 152 75 90 53 116 13 85 78 95 54 188 79 159 18 79 5 107 38 131 9 87 88 102 101 160 44 49 33 143 8 126 114 167 23 25 108 167 90 96 41 129 33 175 90 187 40 80 25 85 20 40 60 140 20 35 21 140 77 162 127 174 10 24 3 53 22 92 67 122 25 187 95 163 122 171 87 156 121 165 7 58 154 183 170 180 59 68 163 167 157 169 148 195 49 107 118 134 41 87 116 194 48 160 124 196 118 170 116 160 166 171 110 156 85 153 76 125 59 132 52 87 2 165 64 158 …
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

Example 2:

Input: 1359 550 116 290 568 1296 498 1134 175 695 438 1053 85 562 40 770 76 294 682 1254 342 556 540 1112 593 1352 513 1098 477 494 1042 1288 505 620 817 994 134 1058 397 732 629 969 343 765 469 1159 913 970 79 135 351 1085 316 1016 433 736 606 963 453 1349 802 898 96 972 934 1157 109 1004 448 820 566 711 449 1189 86 178 588 900 576 590 882 1337 722 866 26 916 50 498 531 819 924 1035 900 1083 579 1219 336 455 381 601 392 1352 469 1048 208 774 244 1202 1122 1157 974 1253 743 1032 797 1017 183 354 612 1254 473 1012 782 1209 300 560 936 1251 862 1030 857 1119 215 425 1161 1222 359 493 5 459 195 1225 124 286 154 238 263 824 308 1014 488 567 480 1260 214 866 125 499 659 1049 186 824 306 1232 92 592 163 280 949 1059 222 230 862 1127 309 1210 465 1106 319 519 39 334 20 1026 321 815 90 723 134 1351 930 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 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: 251 490 155 172 123 139 25 54 8 85 17 211 4 45 197 213 97 139 244 250 174 235 141 237 110 144 38 119 12 216 51 101 37 133 9 244 32 54 74 139 144 153 31 230 2 123 225 250 31 97 161 224 32 42 126 148 55 72 25 83 41 217 18 91 101 248 2 185 38 172 18 202 96 222 111 117 57 82 22 73 64 137 45 120 76 205 179 210 53 83 179 224 77 136 88 223 20 209 69 114 16 94 95 118 70 242 15 54 110 153 33 70 101 209 113 161 12 172 125 201 14 168 95 145 50 122 200 246 55 229 28 225 64 144 112 228 44 92 20 64 64 215 155 188 89 101 115 174 155 184 111 165 79 136 36 120 70 206 20 58 60 143 81 189 178 249 86 211 18 181 1 122 49 231 227 243 127 189 37 62 39 154 3 64 71 155 162 182 201 231 109 129 134 175 125 239 26 165 114 141 65 68 40 44 50 140 125 210 27 157 68 162 90 122 32 204 44 129 55 247 19 74 154 192 139 196 7…
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 <= 1610; 0 <= m <= 1610.

Loading...
Test Cases:No test cases
No test cases available.
The Violet canals of Devi - MEDIUM Coding Problem | CodeTikki