CT63291

Kavya's Golden tunnels

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the poppy fields of Scarlet Plain, someone must win the guild's seasonal contest. This year the task falls to Kavya, armed only with the tunnels register. 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 <= 2846; 0 <= m <= 2846.

Example 1:

Input: 944 2284 209 772 271 765 324 332 735 897 541 631 401 825 330 665 462 702 46 53 15 368 227 760 504 630 38 897 758 888 321 720 793 823 127 842 441 706 200 371 500 594 222 381 653 659 545 784 47 841 342 762 656 782 385 887 227 643 633 770 495 701 250 583 21 740 365 847 193 764 376 904 289 604 420 518 118 320 14 71 22 634 559 841 417 518 53 330 640 703 711 798 493 656 140 624 41 764 77 112 103 308 636 786 80 742 574 759 463 521 7 306 308 522 222 776 605 816 606 649 161 450 541 657 532 601 701 817 214 565 578 606 192 783 727 781 129 653 101 266 505 893 153 473 144 916 160 828 278 473 174 595 219 489 52 421 523 623 369 391 33 93 16 624 32 939 151 378 744 927 267 603 204 937 886 896 476 868 257 868 114 728 147 423 166 454 203 930 111 748 172 214 263 852 20 657 162 698 12 275 531 549 11 695 161 24…
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: 1083 959 420 541 28 488 520 1058 908 1066 131 556 795 798 543 586 807 926 86 863 263 1060 255 299 249 1045 535 958 697 1037 584 1007 27 107 342 382 144 290 199 654 200 747 80 280 181 860 14 61 565 754 420 980 438 1024 147 504 438 455 112 357 278 754 433 676 12 835 214 708 623 722 109 1013 39 715 189 308 27 325 354 966 352 655 258 388 136 198 88 114 105 1071 268 1044 43 859 238 1016 45 152 109 334 127 673 321 625 251 985 34 820 137 737 452 669 73 553 63 197 606 640 80 437 850 897 83 645 306 473 232 945 253 1051 219 877 114 698 302 323 141 331 346 439 20 950 78 268 619 966 129 198 49 173 603 1024 873 916 233 963 877 1038 167 837 256 872 10 465 2 710 534 970 771 778 356 372 38 722 138 896 44 1052 217 748 171 177 7 146 662 997 245 407 726 879 822 865 96 274 593 673 121 982 183 1028 324 488 709…
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: 348 754 48 89 112 322 27 164 89 276 1 146 185 328 162 212 37 185 155 234 16 345 43 316 71 181 11 229 146 307 145 166 89 224 198 302 27 163 84 145 101 237 192 199 248 325 28 108 186 299 119 167 27 295 92 95 131 257 197 287 169 279 8 74 69 338 84 99 96 326 46 120 83 191 131 148 281 338 11 50 11 139 44 217 31 79 20 290 20 285 283 292 10 184 99 180 196 206 31 188 260 344 7 81 19 324 22 239 30 326 61 89 264 345 272 293 99 215 168 346 10 159 228 275 8 27 164 255 232 291 203 338 75 180 28 209 104 218 233 348 42 79 161 342 161 249 313 315 156 236 32 103 147 295 142 250 12 286 207 314 85 257 68 308 193 340 246 330 96 312 110 133 69 73 160 287 270 332 134 195 68 284 50 264 113 323 67 100 183 307 234 317 38 150 237 344 70 162 137 217 16 52 23 207 10 18 181 224 88 157 264 338 20 244 94 170 23 275 35 4…
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 <= 2846; 0 <= m <= 2846.

Loading...
Test Cases:No test cases
No test cases available.
Kavya's Golden tunnels - MEDIUM Coding Problem | CodeTikki