CT47759

Last corridors of Herald

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the pearl fisheries of Nacre Bay opens only for a perfect tally of corridors. Herald means to find out. 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 <= 2179; 0 <= m <= 2179.

Example 1:

Input: 2027 956 216 711 534 1468 445 1083 853 1025 334 1309 837 1367 305 965 682 1530 302 1944 68 858 1247 1653 1284 1447 341 659 234 525 666 1019 428 1727 239 700 27 1836 1272 1462 1 2015 897 1603 353 1291 321 1038 948 985 195 1642 581 881 1187 1409 1316 1399 279 715 820 1527 575 683 887 1866 482 1893 478 1146 502 788 885 947 558 1136 1319 1700 85 869 1762 1891 855 1617 364 404 435 1020 56 227 1093 1705 812 1191 598 1178 797 1700 580 1912 166 521 375 556 979 1134 382 865 919 979 894 1358 760 1217 1754 1761 134 922 727 1033 162 1750 111 124 1800 1919 258 1135 341 1062 221 1319 73 886 1431 1898 441 642 320 551 757 1797 504 1168 897 1487 529 1744 315 1321 157 1883 867 1263 815 1765 1175 1252 1025 1053 1086 1750 38 769 67 1815 542 1516 393 545 139 1883 1073 1671 128 996 1151 1407 799 1071 762 851 17…
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: 1254 377 256 597 106 506 618 649 583 1120 355 559 591 958 789 1208 691 761 939 1050 20 136 563 862 588 754 82 875 511 694 520 870 113 598 1181 1199 174 948 1134 1146 40 874 180 1193 63 234 9 697 48 967 699 1179 482 989 728 850 157 1154 461 1185 122 347 433 479 414 1143 469 1182 630 989 664 1107 1097 1199 183 824 58 253 284 293 1086 1233 392 651 508 1080 457 709 146 1063 4 1254 169 385 677 748 386 797 227 1064 322 595 164 1250 597 1112 869 1022 735 911 125 753 3 1106 798 832 127 916 491 549 998 1211 640 1063 509 583 565 573 567 1198 614 740 487 1056 798 878 723 1102 448 1096 738 1246 911 1057 1032 1119 644 779 518 863 702 742 745 776 589 1224 263 640 664 825 599 744 572 984 894 1107 417 502 593 1007 756 916 224 883 1225 1239 10 269 838 891 120 667 652 1205 3 923 109 358 715 729 1099 1155 26…
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: 187 1266 155 171 127 132 105 141 16 129 12 118 3 143 169 185 159 164 75 118 76 84 87 135 7 98 23 120 33 74 75 180 7 62 91 147 58 177 30 172 23 105 33 91 131 170 89 113 57 132 112 167 3 156 50 94 93 163 93 130 3 54 22 114 55 144 119 177 85 159 59 77 176 182 96 185 41 42 29 107 64 153 18 134 106 183 36 120 74 123 57 81 113 140 84 183 143 177 5 179 65 69 31 41 143 185 73 175 96 119 34 93 119 138 60 75 82 160 158 179 50 135 56 133 98 158 37 136 6 84 13 126 109 147 88 142 27 104 63 94 124 166 30 116 19 32 139 179 93 143 116 154 146 170 126 170 49 105 35 161 171 185 106 133 146 176 34 82 119 147 102 130 6 23 122 177 42 180 48 79 50 51 135 148 54 118 89 149 34 101 94 174 92 130 11 55 88 162 89 185 129 142 81 187 51 54 28 172 129 145 113 114 38 45 86 116 49 63 18 156 50 103 55 64 10 89 3 186 16 22…
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

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last corridors of Herald - MEDIUM Coding Problem | CodeTikki