CT50196

Baker and the Build Order

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The reckoner Baker has been asked to tally the donation drive. On the desk lies a long table of corridors readings. 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 <= 2084; 0 <= m <= 2084.

Example 1:

Input: 268 2075 5 197 238 257 41 191 210 259 3 124 99 194 194 197 22 180 37 254 28 114 126 229 33 79 19 53 107 126 82 176 14 189 54 206 33 88 62 126 34 101 49 139 69 227 89 267 169 247 84 207 192 217 176 204 195 217 208 241 2 260 185 251 162 178 106 163 103 176 40 254 78 253 31 178 93 185 57 139 28 126 6 148 62 231 27 249 27 229 160 208 59 77 66 252 39 107 12 159 230 237 18 266 181 216 2 105 4 259 90 132 8 95 95 164 33 118 49 143 172 173 67 218 163 221 58 174 106 240 33 211 226 228 196 233 175 197 44 148 197 218 109 208 87 197 38 140 207 265 18 121 37 117 135 259 115 210 46 167 172 199 201 243 62 111 88 134 36 181 9 185 78 235 135 156 21 166 80 175 27 142 70 87 27 176 149 186 97 259 115 154 31 260 191 207 51 156 255 261 89 118 115 175 1 250 27 244 189 201 61 233 141 213 111 131 135 141 40 143 52 …
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: 1638 138 942 1279 600 926 1347 1512 596 1315 1392 1591 784 1540 274 351 362 1458 142 1615 173 866 971 1572 121 1376 1051 1237 58 124 24 1347 143 234 186 616 995 1165 139 804 286 1078 886 1478 319 1569 888 1205 399 494 1176 1249 191 425 28 1507 777 1138 209 1309 699 850 85 1468 1113 1140 769 1629 1582 1611 267 684 750 1252 354 1232 252 907 122 249 1130 1623 633 1294 573 1053 159 581 1512 1557 1042 1427 406 988 392 446 461 1084 285 724 1065 1216 397 503 21 1377 507 793 1038 1075 484 1261 874 898 26 955 17 1512 721 931 37 750 372 1323 207 1383 203 1053 177 1391 488 1394 324 433 115 400 550 784 195 1487 692 880 435 1506 62 1631 73 1179 25 1017 412 1146 426 473 324 731 1083 1522 611 1430 1169 1430 1046 1335 751 1609 417 1216 992 1342 566 614 12 1335 680 831 584 1245 429 489 75 1441 42 1288 125 …
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: 1967 469 180 485 387 1100 601 788 991 1187 65 158 409 521 441 1822 209 505 319 1563 551 1651 638 833 1596 1623 1734 1744 168 608 336 1522 803 1596 156 962 825 1099 701 783 1585 1791 1814 1827 496 1316 1604 1680 1720 1830 567 655 38 762 1348 1782 591 716 241 1174 769 1858 251 1070 51 1296 142 1394 782 1740 1163 1365 284 1168 838 1862 125 548 407 508 533 1778 1582 1912 489 1468 1 835 12 37 139 1832 440 1571 625 1458 823 1590 18 1425 220 263 1476 1506 299 1896 506 1012 140 588 137 1945 25 1219 1197 1694 510 1791 564 1750 765 1789 337 1357 586 613 10 473 484 1256 64 968 1191 1875 301 1492 147 473 9 1384 25 671 308 421 677 1790 1106 1595 27 1520 163 1791 557 1449 754 1219 712 1108 36 1081 214 1062 303 1048 700 897 976 1670 691 1096 1015 1826 478 778 1379 1666 469 669 941 1405 202 1356 245 1097 …
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 <= 2084; 0 <= m <= 2084.

Loading...
Test Cases:No test cases
No test cases available.
Baker and the Build Order - MEDIUM Coding Problem | CodeTikki