CT49744

Farmer's Ledger of bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the mangrove channels of Rootwater, someone must optimize the storeroom layout. This year the task falls to Farmer, armed only with the bridges 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 <= 1543; 0 <= m <= 1543.

Example 1:

Input: 1045 1261 289 924 942 984 887 1037 30 231 93 589 419 477 475 1034 54 703 84 1003 257 782 289 430 706 825 237 807 158 1022 452 940 863 1038 419 690 261 320 93 264 376 935 285 523 33 883 25 557 213 387 528 985 78 903 96 262 21 297 571 941 26 693 210 508 151 654 130 843 629 785 663 1006 595 993 457 675 27 951 258 380 329 412 216 293 98 329 147 618 26 498 185 279 296 493 38 985 106 419 13 728 616 978 314 992 126 855 127 664 676 859 697 898 882 885 334 769 25 753 611 974 285 847 178 644 558 908 191 272 594 979 164 744 667 1025 640 975 394 736 879 956 89 937 805 815 527 683 32 150 434 727 585 942 857 992 597 896 644 660 628 916 404 527 205 847 26 792 272 605 242 332 369 804 381 900 112 821 347 1003 136 653 785 951 407 675 227 1043 536 631 54 476 56 883 126 200 391 674 48 688 594 984 118 662 820 …
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: 95 458 52 55 37 77 9 89 45 87 71 79 39 44 28 40 42 66 23 31 53 66 71 87 40 83 61 66 30 33 38 53 42 68 34 84 18 22 45 49 23 60 75 80 48 71 23 93 12 42 11 68 72 90 25 43 63 90 4 23 68 82 14 87 47 88 49 73 28 88 17 18 15 49 2 67 57 79 41 87 47 79 44 52 10 26 55 87 64 71 14 36 57 88 12 55 25 76 34 42 44 62 61 75 30 47 5 82 57 84 18 55 52 54 50 88 34 90 1 75 77 87 65 88 8 51 56 71 45 59 69 91 14 35 24 64 3 6 49 69 34 93 32 45 56 62 68 90 52 64 2 71 40 89 6 42 39 65 41 48 20 84 32 80 16 69 6 79 55 66 62 93 37 67 59 66 17 79 29 43 31 67 7 26 35 85 17 44 43 61 3 51 26 60 30 83 39 42 81 85 16 45 28 58 15 82 1 52 1 26 9 40 15 80 30 34 55 64 26 81 46 61 50 83 15 79 6 69 4 49 62 80 75 92 81 90 76 89 27 65 72 88 34 92 17 34 51 81 44 54 57 59 45 84 43 47 16 91 14 47 63 91 11 66 55 89 50 60 28 83 42 86 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

Example 3:

Input: 547 827 193 485 285 383 379 402 172 287 259 443 70 292 353 482 26 39 366 371 382 426 192 228 248 436 107 335 242 535 222 244 502 537 91 463 300 350 82 150 133 272 293 449 270 529 25 46 115 350 190 431 62 74 171 215 59 440 8 411 43 290 18 413 209 454 106 264 200 237 375 516 33 88 135 179 52 259 216 537 152 529 69 98 488 512 3 272 256 419 33 74 30 134 423 547 117 421 73 114 192 255 65 213 48 401 121 424 20 507 125 466 400 450 99 499 287 331 79 246 156 327 120 455 73 216 125 180 190 505 27 469 122 469 111 309 258 377 295 383 124 190 444 535 96 305 3 210 336 501 325 424 147 162 277 357 124 383 391 519 187 414 151 498 19 31 253 388 458 484 151 269 9 481 162 243 78 412 156 223 376 397 39 357 334 501 141 362 33 140 168 304 190 247 355 411 136 209 200 214 221 278 174 223 301 418 90 321 252 525 90 …
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 <= 1543; 0 <= m <= 1543.

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