CT48301

Tara and the Ember canals

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Tara inherited the mint at the singing sands of Echo Dunes along with its curious bookkeeping system for canals. Time to make sense of it. 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 <= 1801; 0 <= m <= 1801.

Example 1:

Input: 401 316 91 353 246 336 141 159 241 265 106 271 237 298 46 288 57 369 117 316 177 258 74 163 300 395 91 97 71 258 324 367 176 184 57 223 34 186 221 245 312 397 85 314 137 244 163 190 97 349 164 297 112 172 71 374 77 166 105 218 60 192 115 374 168 359 252 254 31 373 129 254 20 111 131 187 38 149 4 149 48 294 54 390 120 401 224 287 210 307 360 375 316 352 308 399 93 134 29 202 205 215 80 130 68 368 136 199 80 315 273 387 75 191 150 231 269 292 38 107 90 101 103 268 2 32 267 327 221 282 191 256 81 377 340 369 177 280 324 390 320 369 85 378 21 269 36 339 179 305 41 387 109 336 171 246 85 120 192 371 196 238 134 233 50 160 6 341 288 401 211 341 1 312 251 314 281 282 102 328 59 385 80 159 114 299 152 271 87 128 81 287 157 168 219 258 96 288 82 148 39 357 23 136 102 388 280 344 97 366 268 363 1 38…
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: 1222 31 1047 1076 614 969 370 693 2 1000 216 402 362 723 41 378 205 981 244 835 472 880 38 96 39 900 265 730 269 436 190 1160 297 432 248 311 474 1029 989 1115 945 1100 907 1214 681 891 714 1130 280 909 849 879 484 718 417 758 375 974 166 753 604 707 424 548
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: 1152 1715 794 1092 44 864 352 548 699 725 99 723 589 869 493 757 571 1109 387 971 552 734 904 1008 612 799 285 1054 606 760 546 876 196 277 211 425 676 1125 10 272 101 443 971 1000 540 567 366 619 44 576 304 407 53 982 1022 1104 973 995 558 1060 673 1076 639 780 708 950 295 603 485 1017 353 836 490 1091 211 698 13 70 489 892 105 1012 127 472 558 637 172 456 743 799 213 347 67 865 434 930 870 887 56 718 420 1090 677 1014 252 770 343 1041 42 1002 107 1128 252 952 273 490 476 1019 638 874 96 1090 687 803 59 342 500 712 9 122 282 1127 651 1072 37 241 413 754 340 547 678 819 6 692 766 929 265 817 561 614 154 913 356 1066 148 1123 40 795 104 994 145 589 300 570 215 610 165 429 558 992 59 137 734 797 143 893 107 517 315 424 101 217 277 698 130 157 466 1094 608 830 38 421 651 791 370 742 708 893 7…
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 <= 1801; 0 <= m <= 1801.

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