CT40962

The bridges at Grapehollow

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the terraced vines of Grapehollow pays by the answer, and Smith intends to earn it. First: the full register of bridges. 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 <= 3378; 0 <= m <= 3378.

Example 1:

Input: 2863 10 1434 2612 1940 2844 476 1188 320 2062 1877 2723 622 1585 82 2625 1621 2397 130 1730 1747 2450
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: 308 2276 103 220 159 299 131 303 89 235 119 212 106 294 69 232 91 187 81 167 59 178 98 100 183 266 46 287 69 208 96 235 139 207 23 277 188 220 100 252 132 287 41 251 78 197 11 46 91 306 222 291 142 248 283 287 18 158 17 256 134 162 41 107 135 286 47 157 119 197 109 205 131 193 116 237 17 153 136 142 35 56 69 135 66 281 34 223 104 182 32 169 105 158 40 182 81 102 61 262 188 277 122 172 43 277 28 250 160 204 191 289 12 158 75 267 153 253 209 284 48 220 101 209 76 237 88 153 68 135 84 225 116 155 272 292 85 279 128 173 104 142 226 302 93 185 132 140 173 212 14 147 80 189 211 248 4 178 31 212 121 300 260 276 33 302 146 244 51 201 142 155 83 122 75 255 55 230 13 42 121 264 177 188 15 99 12 111 180 204 144 229 73 115 164 276 195 235 79 239 229 296 258 300 224 304 199 296 175 259 220 303 39 65 29…
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: 1685 2611 551 1207 191 432 889 1573 1073 1423 54 1301 489 805 387 1387 899 1215 835 1373 1298 1645 406 781 290 1040 464 1078 454 723 963 1253 485 1359 471 752 869 1384 1255 1427 660 771 412 667 433 666 993 1063 157 425 246 1363 536 1177 792 1045 105 111 1113 1135 1290 1319 1217 1576 258 512 1464 1506 1212 1575 959 1470 201 1120 862 1339 1127 1671 611 1576 153 1662 533 1074 49 511 53 753 57 65 530 909 1257 1683 438 1156 251 577 597 981 138 149 100 1014 543 1226 126 400 1009 1666 452 616 815 1404 152 1291 903 1606 1341 1680 1503 1516 861 1512 909 1133 445 1128 1421 1607 320 559 642 698 949 1154 124 1374 912 1360 552 1121 879 1315 860 1600 829 837 369 1197 321 1220 355 465 788 1402 826 1563 474 1416 472 1476 597 1121 313 1127 1146 1376 26 922 95 1494 119 1547 1142 1329 678 1318 153 1634 670 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 …

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The bridges at Grapehollow - MEDIUM Coding Problem | CodeTikki