CT62862

The Build Order of the Pale roads

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Dora the dispatch writer watches over the glass towers of Prismhaven's stores of roads. 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 <= 2617; 0 <= m <= 2617.

Example 1:

Input: 1738 1001 1362 1729 809 1443 329 980 618 1449 1085 1604 1334 1482 824 872 799 1004 594 771 274 723 40 823 248 321 1574 1732 356 795 166 998 1002 1713 962 1341 860 1001 1253 1562 1287 1734 688 1114 312 695 1187 1668 103 1554 276 488 1237 1661 1013 1099 848 1088 237 523 781 1483 531 1038 605 1374 26 826 382 1330 707 1629 709 1246 223 333 219 1081 16 1114 521 907 664 967 278 311 316 554 1096 1460 605 1382 1217 1276 1197 1470 43 1632 581 793 982 1550 154 1415 1071 1271 773 804 506 1246 1155 1190 637 1716 488 1052 1236 1540 1166 1533 340 646 1404 1587 48 618 159 1293 340 875 89 620 931 1261 648 1162 696 1429 213 573 287 1454 1206 1639 81 894 5 797 101 418 881 1203 1361 1491 260 1123 1584 1604 1093 1573 559 1171 8 1355 391 1724 951 1595 468 952 106 1118 261 800 371 994 191 698 511 1477 221 290 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 2:

Input: 2509 5 163 422 1686 2495 575 1946 1717 1795 1976 1981
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: 397 69 220 332 180 328 270 353 153 340 134 314 44 121 83 378 303 354 309 370 40 192 56 63 18 130 62 192 6 330 227 244 99 171 133 302 189 310 135 163 100 277 253 266 284 296 174 347 139 158 153 289 168 334 357 359 240 318 8 331 111 241 289 336 208 210 2 61 29 153 171 238 54 177 179 248 292 350 185 250 116 220 81 195 340 344 23 200 167 364 124 396 337 338 72 173 46 178 222 288 22 196 132 298 75 240 180 262 110 358 10 53 338 384 55 236 22 212 64 79 305 358 323 376 18 259 137 176 48 371 230 306 80 102 253 316 372 376 289 393
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 <= 2617; 0 <= m <= 2617.

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