CT37940

The Build Order of the Misty routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the observatory of Starfall, Sable studies rows of routes entries. One clean number will settle the guild's oldest argument. 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 <= 3686; 0 <= m <= 3686.

Example 1:

Input: 1332 470 145 403 273 499 47 1176 79 802 526 568 17 547 616 1239 1188 1324 1226 1298 120 357 325 528 476 917 602 1100 497 526 123 223 148 1024 164 787 582 930 366 1235 644 821 869 1138 775 978 372 1192 286 1217 772 1082 19 618 150 307 466 1286 608 729 105 535 14 1261 53 124 56 1299 236 752 443 1129 901 1049 697 1272 475 1296 460 753 283 734 179 906 700 1092 72 283 958 1180 334 630 474 1090 372 858 13 1265 84 177 526 1172 407 969 846 982 89 865 833 947 645 1040 48 810 1144 1288 40 281 798 807 304 1027 50 574 199 1272 316 539 523 1175 300 960 880 1208 447 844 241 676 485 529 1060 1108 645 647 200 1244 37 554 211 344 604 791 170 293 258 640 351 352 440 1135 501 961 155 932 88 729 217 245 83 1042 1045 1198 401 563 74 122 690 777 397 1063 559 1000 868 1299 414 1016 25 1141 435 1141 183 1319 923 …
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: 814 25 498 814 345 782 27 84 71 319 125 384 453 610 88 124 663 805 552 604 38 650 512 739 292 502 300 339 101 667 257 722 63 288 725 734 224 764 43 701 575 626 48 569 10 106 343 524 23 387 72 775
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: 976 743 69 723 114 475 146 645 291 784 182 684 226 954 477 799 46 227 21 50 480 487 502 961 802 898 29 860 303 328 452 571 7 751 561 577 249 827 112 669 249 872 384 891 495 628 197 601 202 558 168 782 89 648 390 478 361 534 299 922 240 352 207 325 138 557 238 777 605 959 302 737 694 695 19 690 627 852 638 805 48 115 327 595 27 836 473 541 177 353 199 753 398 719 214 880 260 501 511 669 429 783 437 913 311 582 632 815 220 537 164 442 764 926 787 829 101 404 19 23 358 483 180 858 829 958 205 705 513 873 438 460 553 562 84 139 125 239 296 772 154 533 444 818 99 584 59 113 222 543 178 252 663 715 74 296 486 534 540 807 170 457 166 840 240 437 802 901 247 311 142 370 469 475 71 438 164 910 227 570 17 259 586 846 104 450 34 907 180 962 471 930 104 926 316 633 111 831 387 840 120 759 65 626 418 9…
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 <= 3686; 0 <= m <= 3686.

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