CT50916

The tunnels at Saprun

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Weaver found an old ledger of tunnels in the counting house attic at the maple sugarbush of Saprun. The margin notes pose a precise question. 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 <= 2649; 0 <= m <= 2649.

Example 1:

Input: 2156 2549 427 967 31 954 196 1677 290 670 1129 1552 33 2054 1089 1237 1238 1271 141 1537 1824 2030 241 1974 430 773 426 1251 970 1926 382 1191 1192 1831 1809 1915 237 304 261 956 926 1737 39 1972 12 1939 1745 2098 1465 1546 986 2058 398 419 102 528 25 561 1822 2150 23 402 1231 2091 678 1247 1248 1302 431 937 1305 1528 1670 1709 1468 1724 606 877 1539 2041 1141 2050 1238 1723 977 2006 335 945 920 1607 778 908 566 636 1498 2109 351 1592 2052 2092 292 955 1 1355 350 1002 1303 1450 131 1920 548 1347 747 750 51 129 819 2068 1190 1582 1532 1623 557 1376 644 1526 422 1540 518 2088 860 1210 638 1401 831 1387 441 815 263 1446 723 948 1417 1683 521 674 24 285 1165 1347 895 1307 1060 1316 67 294 87 1354 254 584 1369 1617 1187 2156 1297 1442 669 1127 1397 1478 197 1644 973 1572 378 532 1423 1539 328 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: 1110 1080 660 800 88 715 67 530 74 721 56 834 162 943 366 563 130 900 26 598 184 692 249 661 320 1078 239 514 234 462 536 737 245 275 160 851 412 1094 84 812 371 918 539 1047 770 863 209 802 694 1037 434 519 267 465 159 752 568 834 90 638 254 526 378 968 59 517 350 1048 758 970 248 876 46 48 369 756 212 964 346 1018 827 907 523 688 313 804 124 170 331 550 440 650 248 278 640 684 577 808 545 1032 115 1018 357 657 30 407 279 806 272 841 302 898 178 222 3 1101 464 606 382 1002 390 720 9 717 177 374 432 712 40 412 769 998 503 712 559 896 429 493 275 588 52 54 36 385 415 670 468 669 710 1079 695 758 894 948 366 879 198 390 185 310 339 467 245 305 55 92 182 705 196 669 36 434 384 650 278 622 350 431 25 187 718 853 170 1032 770 810 560 931 786 918 139 945 153 269 22 1023 417 860 50 456 366 377 62…
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: 363 2240 217 359 135 161 111 208 9 354 175 197 278 307 15 353 237 349 140 303 32 249 45 105 92 170 336 342 7 143 41 296 159 175 115 173 84 253 37 350 27 223 222 242 82 157 36 277 24 204 87 123 303 309 43 285 197 301 288 326 156 286 170 242 44 138 224 241 125 229 210 281 36 44 276 311 245 329 143 159 70 196 109 357 21 181 164 261 195 346 9 228 254 324 121 171 132 362 89 273 139 346 146 217 204 277 27 182 85 117 231 333 113 329 43 235 49 53 226 352 5 251 268 294 39 199 59 351 160 234 81 183 8 331 109 156 182 235 305 340 192 310 71 217 14 73 218 239 162 266 119 125 139 291 1 346 268 348 271 295 15 239 135 245 44 121 193 194 184 325 41 173 178 356 33 200 98 204 5 204 141 188 149 178 9 120 162 282 79 185 59 106 285 324 211 268 133 279 125 240 60 68 149 307 76 251 283 359 35 359 46 326 106 347 2…
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 <= 2649; 0 <= m <= 2649.

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