CT46068

Peddler's Timeworn routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the garden city of Petalbrook, someone must forecast next month's demand. This year the task falls to Peddler, armed only with the routes 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 <= 2511; 0 <= m <= 2511.

Example 1:

Input: 1656 177 165 1180 92 1010 343 1487 1038 1357 1226 1254 170 1553 770 1220 1014 1318 1263 1486 614 1312 521 550 50 808 311 1143 58 1317 51 987 182 562 678 1050 738 767 493 1129 1354 1608 145 1544 1564 1635 902 1338 631 1059 1529 1555 90 1135 400 1175 58 855 504 1338 712 1400 1342 1642 1090 1519 113 1604 1543 1641 112 864 267 1359 434 1096 292 567 571 1144 304 1512 893 1402 887 1413 18 1582 977 1393 377 1470 10 755 652 720 72 655 1333 1420 714 1091 672 995 687 1600 1306 1352 159 648 395 636 8 558 882 1131 187 1598 1251 1340 1133 1461 1223 1266 23 577 39 298 343 497 822 1047 51 1437 695 1517 1178 1570 1060 1430 1367 1516 237 1025 224 1145 582 1564 1194 1642 874 1068 1082 1629 79 1042 1346 1588 1 573 554 1575 117 1256 142 863 245 1444 50 588 508 690 1199 1467 9 604 97 1086 310 1244 90 1396 899 …
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: 799 294 165 431 83 676 42 96 221 555 289 637 35 751 730 781 103 795 64 221 407 414 478 719 192 681 39 211 66 208 231 446 431 579 372 503 113 355 304 478 659 795 254 326 341 594 54 155 339 579 501 594 77 797 405 416 372 590 88 763 163 433 462 620 55 641 421 443 337 504 202 363 44 508 143 665 29 242 78 533 197 695 218 795 188 682 72 439 583 636 1 574 67 330 41 400 385 571 638 758 73 573 671 798 119 457 143 573 375 574 7 311 603 604 80 573 152 523 24 710 3 313 207 491 10 388 582 764 671 720 159 276 27 529 269 640 38 526 497 702 278 405 199 656 144 392 166 178 59 226 40 285 65 100 227 636 120 619 638 642 540 618 470 609 167 194 109 781 402 495 315 610 217 545 363 673 223 484 27 366 390 423 312 716 286 730 206 526 82 211 568 592 28 36 126 689 552 671 294 587 206 464 492 554 9 198 245 255 50 701…
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: 556 1675 192 198 428 508 441 547 270 432 77 395 326 443 128 464 149 475 313 358 216 482 20 302 196 207 332 410 10 556 104 154 116 437 340 357 33 125 205 465 120 442 297 446 333 460 164 555 276 314 406 470 89 550 145 361 397 416 167 344 4 402 250 266 217 533 316 420 118 218 135 148 400 455 49 110 245 266 109 175 168 555 52 262 228 360 145 407 98 185 292 508 9 74 351 427 9 333 46 396 44 353 251 526 202 315 84 401 216 406 367 376 13 408 69 118 107 406 69 313 197 540 63 485 160 494 461 507 127 440 150 304 204 220 320 508 260 381 20 36 40 411 309 352 5 247 167 495 66 388 77 278 335 352 294 410 306 310 201 474 18 71 370 397 1 541 200 257 136 400 457 514 283 487 64 465 156 472 311 350 456 457 142 463 157 521 175 398 259 280 299 381 284 374 48 112 242 555 26 391 364 436 1 258 27 308 232 468 68 529…
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 <= 2511; 0 <= m <= 2511.

Loading...
Test Cases:No test cases
No test cases available.
Peddler's Timeworn routes - MEDIUM Coding Problem | CodeTikki