CT41107

Teal tunnels Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Lamplighter the clerk watches over the forest village of Briarthorn's stores of tunnels. 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 <= 1592; 0 <= m <= 1592.

Example 1:

Input: 117 1252 35 99 28 78 39 65 3 49 67 105 48 68 91 112 44 76 25 77 23 95 20 95 22 106 57 96 41 110 18 78 43 83 29 102 86 113 21 87 42 111 40 112 44 94 104 115 4 25 20 105 35 98 19 104 50 67 1 84 69 90 13 42 60 84 42 75 39 112 3 18 96 116 60 111 18 92 6 32 20 86 64 103 86 103 96 112 84 110 78 95 111 114 2 62 24 104 15 87 40 109 71 112 27 51 82 95 31 106 33 44 16 35 22 32 77 83 53 112 3 4 8 85 36 110 53 83 42 53 47 68 63 74 66 95 15 73 70 101 22 68 12 19 12 72 70 89 32 100 17 73 37 45 69 76 70 100 93 108 40 86 92 112 28 40 24 77 78 91 33 68 40 76 35 103 74 79 36 67 22 59 77 110 29 92 83 99 4 9 12 56 88 104 2 33 77 80 17 107 1 74 38 102 63 90 88 109 57 62 50 73 4 62 7 63 4 76 12 42 6 7 82 94 41 50 22 58 18 21 4 63 22 61 23 77 24 109 2 71 42 44 7 19 81 94 10 11 27 32 61 112 75 115 6 13 62 68 8 63…
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

Example 2:

Input: 92 168 4 53 21 32 36 77 22 64 20 30 47 83 63 91 4 80 46 59 61 91 34 62 20 51 24 55 50 91 6 65 34 54 14 54 21 70 21 65 34 59 4 86 3 31 35 74 2 71 83 90 74 84 49 84 39 74 38 75 12 16 7 82 9 74 21 81 14 60 53 91 62 80 27 70 2 58 7 40 4 9 53 54 30 61 36 59 48 72 16 37 20 61 14 35 44 86 48 87 28 62 50 59 52 60 64 69 58 82 43 55 18 75 76 86 13 21 80 86 23 92 3 68 17 83 68 69 5 41 10 39 17 82 8 37 33 87 2 51 69 75 10 37 24 26 56 78 21 83 1 78 75 91 12 78 4 7 18 77 41 58 9 35 19 56 22 81 44 76 26 43 10 22 15 44 50 67 29 60 10 13 2 15 27 46 16 64 27 39 74 85 7 78 46 67 22 48 52 78 32 58 3 24 44 69 5 59 31 60 40 57 33 88 22 53 47 89 5 55 39 85 71 72 51 54 58 91 50 52 16 57 15 34 50 75 42 57 42 86 59 78 1 57 8 38 2 38 38 68 9 58 29 51 9 90 82 91 47 48 24 61 84 89 4 83 25 84 3 66 33 72 57 65 4 35 10 8…
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

Example 3:

Input: 1202 385 247 817 344 987 467 801 745 1085 282 351 706 973 232 391 587 596 76 356 235 508 111 633 201 456 183 342 53 243 640 1045 435 528 589 908 68 339 73 984 652 1055 642 955 153 434 988 1181 739 937 304 498 261 727 18 503 471 791 734 1106 358 1121 363 668 269 1052 277 719 242 1028 211 477 22 744 303 694 180 531 462 1123 45 1073 138 937 805 839 274 778 51 337 48 272 1186 1194 498 823 158 1083 67 320 240 1128 418 1161 100 998 236 1118 108 583 955 1148 490 1100 883 1192 825 977 59 630 619 902 526 587 27 317 322 746 820 959 140 283 645 989 511 807 569 844 213 744 199 1100 87 424 175 213 164 1175 103 1083 119 1011 193 624 13 310 252 334 590 1174 189 572 336 1191 219 1111 668 1194 171 392 851 961 685 768 118 627 527 1013 162 400 176 901 243 399 59 1058 97 616 946 1104 467 1105 1092 1133 68 978…
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 <= 1592; 0 <= m <= 1592.

Loading...
Test Cases:No test cases
No test cases available.
Teal tunnels Build Order - MEDIUM Coding Problem | CodeTikki