CT60533

The roads at Ashfall

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the ember dunes of Ashfall with crates of roads, and Librarian the chronicler must account for every last one. 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 <= 860; 0 <= m <= 860.

Example 1:

Input: 221 812 77 156 8 34 1 133 127 199 5 81 27 102 35 193 16 196 17 111 71 173 53 190 34 202 34 64 102 218 72 177 1 134 8 204 26 125 42 168 34 166 91 164 105 206 118 167 50 110 41 74 18 194 80 128 76 168 94 121 130 132 87 144 136 192 5 208 82 215 47 55 112 215 12 205 161 194 82 110 90 171 31 55 30 210 16 168 60 176 187 194 167 188 3 103 213 219 28 116 140 211 150 177 91 175 71 125 124 212 137 168 27 133 54 121 36 221 63 115 63 217 179 195 22 159 114 116 133 188 30 70 62 209 28 148 109 133 119 141 99 205 115 182 76 176 73 81 134 216 11 160 92 134 100 212 98 143 101 217 4 10 37 92 191 205 71 74 72 79 93 133 166 187 107 157 40 162 55 62 17 159 21 146 33 130 93 164 135 210 165 192 129 187 29 86 126 181 10 19 132 172 26 135 115 132 84 129 27 76 40 76 40 145 162 172 25 47 39 46 126 182 60 65 68 176 3…
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

Example 2:

Input: 89 243 15 82 24 75 30 84 37 84 10 19 2 82 42 57 1 67 22 33 21 56 50 59 18 75 15 65 27 30 81 89 53 60 3 15 24 66 10 55 20 22 7 79 14 60 14 19 16 78 3 48 9 10 1 51 26 70 70 71 31 50 28 63 15 30 40 63 34 65 23 29 62 80 1 64 87 89 23 59 38 81 2 18 41 78 25 82 13 59 1 31 70 89 48 75 14 22 44 71 7 50 65 81 7 65 40 52 18 60 6 64 7 19 8 51 15 27 22 56 1 15 11 14 28 88 2 13 14 62 7 22 64 73 70 81 17 47 5 33 3 49 47 62 14 32 13 73 49 60 52 65 20 77 23 25 28 69 16 19 60 83 14 38 31 36 25 68 5 27 19 47 11 30 24 27 36 64 1 20 51 67 18 55 18 65 68 77 8 73 10 66 77 89 38 53 30 79 14 23 9 59 39 69 18 85 28 51 35 84 6 85 46 88 28 50 14 25 33 69 36 53 18 69 36 67 26 69 67 71 83 87 45 48 3 36 1 28 5 18 5 60 14 75 4 81 20 55 41 83 39 83 21 69 46 80 28 64 13 32 46 87 71 87 11 51 13 19 14 33 13 30 44 52 9 72 48…
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

Example 3:

Input: 175 528 41 54 72 112 112 157 72 121 25 52 116 175 119 166 80 144 67 126 44 90 51 99 65 133 156 166 135 144 131 159 14 60 114 173 61 65 2 25 112 130 99 113 30 88 64 146 101 167 22 70 135 158 41 168 81 126 1 55 37 115 38 170 85 97 28 163 11 31 22 33 155 172 19 23 81 90 60 150 123 124 26 42 122 170 9 29 42 160 31 81 20 97 139 163 96 173 72 130 17 63 67 149 6 120 52 87 155 171 61 103 104 150 32 82 10 19 111 135 96 130 35 79 39 138 53 172 5 72 79 87 96 99 131 148 35 93 52 159 49 83 22 149 29 168 3 150 95 96 20 28 105 112 22 147 28 166 76 165 15 154 36 170 98 146 36 128 57 74 23 165 57 142 6 27 128 136 52 140 73 131 42 139 19 55 18 139 53 107 35 173 25 140 73 148 65 68 11 24 3 46 63 147 128 143 21 114 45 122 10 98 19 132 31 89 71 100 119 146 47 160 64 107 124 150 44 58 5 146 25 143 22 75 84 88 3…
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

Constraints:

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

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