CT61966

Jarl's Ledger of canals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The quartermaster Jarl has been asked to document the rare sighting. On the desk lies a long table of canals 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 <= 1719; 0 <= m <= 1719.

Example 1:

Input: 1180 954 144 1107 48 335 464 497 145 812 320 971 122 991 27 107 482 597 639 910 996 1011 368 790 541 984 344 904 99 1057 918 996 913 976 337 354 778 799 316 842 254 359 684 829 113 315 2 72 410 714 617 810 943 1037 30 54 57 1152 782 1053 337 872 185 556 567 797 149 451 109 738 368 1121 471 826 509 841 588 700 201 491 413 914 545 1077 771 1123 156 922 698 793 185 412 590 836 182 497 658 874 434 782 582 669 190 520 394 1073 409 1161 283 554 77 124 35 87 497 952 24 751 295 468 209 256 441 718 84 903 397 1110 908 941 158 753 534 673 263 695 289 993 124 876 261 751 259 905 698 983 776 880 217 1042 211 735 251 801 748 913 244 476 217 405 464 1136 577 612 158 750 249 266 318 478 714 783 766 899 781 1169 347 749 406 552 288 1021 547 993 752 999 221 751 232 1097 36 353 173 755 54 93 376 889 452 900…
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: 306 778 116 189 160 268 59 216 28 208 178 266 234 305 124 225 145 238 69 83 47 160 72 136 186 295 43 280 118 275 51 140 61 197 34 178 14 86 135 148 123 268 6 291 17 253 68 105 147 174 186 296 43 51 104 166 36 90 8 162 248 251 223 249 83 208 98 287 32 100 75 263 105 261 40 297 111 175 61 186 4 231 232 259 17 218 57 205 211 230 71 287 59 252 87 229 205 208 16 145 80 95 56 86 102 228 35 113 31 258 203 302 156 295 14 232 29 170 99 183 81 216 126 145 135 281 111 181 70 151 36 108 223 265 219 297 124 142 152 159 90 164 25 298 280 287 48 227 156 270 4 245 26 30 162 177 106 163 31 283 149 260 62 303 121 197 219 306 65 218 19 154 203 262 254 277 11 142 109 302 236 266 45 115 113 167 236 238 24 218 91 300 230 247 213 290 87 227 234 241 14 271 66 239 26 117 138 272 63 303 106 183 74 82 121 210 185 23…
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: 1252 752 160 314 630 1223 712 1082 527 618 1098 1101 789 1221 1076 1145 294 846 9 500 680 808 322 513 40 281 179 1216 210 221 358 615 498 1241 676 1120 441 1031 655 1240 780 963 272 634 112 419 45 174 30 1030 80 588 970 1219 385 1118 364 482 490 499 815 1077 555 767 166 1143 595 877 901 945 997 1107 112 685 77 820 329 401 116 485 9 453 614 1201 428 1097 106 416 64 177 212 462 118 269 180 1148 466 1145 1010 1198 158 1246 594 602 298 375 183 520 32 502 179 199 134 167 564 965 382 470 61 875 213 731 615 840 210 830 115 552 129 352 500 696 485 685 350 1239 697 934 588 793 502 710 409 1112 262 909 485 684 397 493 506 663 65 156 632 1233 444 652 151 583 196 778 131 636 411 556 213 517 323 1201 158 610 48 285 754 765 982 1028 297 474 158 519 422 682 609 692 100 544 756 1081 387 852 335 1212 195 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 <= 1719; 0 <= m <= 1719.

Loading...
Test Cases:No test cases
No test cases available.
Jarl's Ledger of canals - MEDIUM Coding Problem | CodeTikki