CT52800

Last bridges of Jatin

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Jatin runs the ropewalk at the valley of Misthollow. Today the books show a list of bridges, and the numbers must be worked out before sundown. 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 <= 1611; 0 <= m <= 1611.

Example 1:

Input: 1201 1523 723 1159 231 1188 863 864 739 1054 59 940 31 671 160 251 1025 1153 199 869 198 854 387 712 259 503 825 1016 731 858 284 1132 10 1027 410 414 208 908 711 854 727 1135 336 1051 367 825 537 870 250 284 222 224 211 304 397 684 708 1009 868 962 356 1195 533 561 124 563 661 798 248 633 570 607 150 368 437 721 189 659 770 1110 174 956 625 833 204 412 871 1128 55 919 880 892 869 900 532 1175 242 507 395 417 224 308 595 605 433 1179 97 615 520 1063 43 1088 712 811 8 524 97 1146 578 745 730 916 491 1197 259 276 945 1195 416 731 46 934 683 1119 492 1176 277 766 377 861 425 766 855 857 293 302 923 1053 304 899 56 870 450 519 170 474 876 978 584 907 226 953 168 862 243 1071 1028 1124 400 500 955 1104 591 786 99 472 419 703 704 1089 55 778 154 1193 116 993 482 508 388 957 288 411 32 748 422 70…
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: 1182 1061 206 563 613 1085 59 561 107 916 1095 1168 129 653 676 754 609 638 465 918 361 506 180 992 619 840 230 302 194 215 843 952 902 960 305 461 2 1013 545 1063 266 688 157 988 81 612 191 486 706 1179 458 1050 37 519 540 1032 466 769 19 925 28 236 689 1151 440 812 130 632 239 383 47 223 544 919 129 306 431 469 118 195 720 780 4 910 112 114 800 1046 195 402 696 750 473 655 579 751 907 1071 15 80 200 454 109 270 161 818 789 1136 505 1143 170 206 146 722 516 1015 108 673 579 974 739 1025 49 469 664 1105 474 962 162 613 394 535 547 770 3 1100 559 985 854 932 22 679 399 1136 14 955 776 994 345 816 325 641 758 1178 521 1002 51 499 351 653 31 265 306 850 237 481 3 1031 303 872 208 1134 244 1159 195 414 155 904 525 546 365 1015 58 1103 545 939 207 1177 347 500 687 1153 615 967 865 921 313 452 4…
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: 90 1072 25 75 31 48 34 41 11 77 54 68 13 72 12 28 33 41 56 59 26 60 58 82 5 10 14 41 41 55 2 52 26 49 4 11 78 79 2 46 36 51 21 36 16 53 28 46 41 45 7 18 14 65 29 34 32 61 9 34 2 16 6 86 82 86 9 78 4 29 53 88 8 19 14 40 11 89 11 19 27 87 28 73 17 29 17 57 1 10 4 83 16 81 33 68 41 87 88 89 10 12 42 66 16 78 62 84 33 44 60 66 57 90 17 74 21 32 28 50 12 60 46 81 73 79 12 34 30 44 22 35 29 54 11 82 44 59 33 66 28 82 3 84 6 40 1 23 27 66 24 56 54 64 23 64 4 48 50 51 19 22 58 62 11 49 3 36 28 66 45 67 18 65 17 40 2 74 54 65 3 69 16 90 82 85 45 90 45 68 43 83 41 76 30 72 67 83 9 81 32 57 26 31 45 61 74 80 77 80 36 86 47 81 50 60 39 81 42 87 3 33 54 74 40 44 25 53 27 56 37 60 17 28 14 78 59 61 25 32 61 80 15 87 11 81 21 38 71 81 47 58 57 61 33 46 47 53 15 22 3 20 11 54 38 63 12 70 18 81 19 52 37 87…
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

Constraints:

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

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