CT49953

Ivo's Build Order Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Ivo found an old ledger of tunnels in the apothecary attic at the shale slopes of Greystone. The margin notes pose a precise question. 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 <= 1861; 0 <= m <= 1861.

Example 1:

Input: 1443 227 956 1279 297 419 47 502 538 1398 1204 1429 658 722 919 1341 1179 1344 112 1111 653 812 318 1350 198 834 501 1229 109 450 110 1399 535 1015 627 1180 390 725 731 1364 321 380 564 907 173 1027 689 735 46 943 33 775 372 767 375 1410 710 1316 605 1263 809 832 917 932 303 907 311 1283 827 855 335 1206 847 1105 34 618 325 351 340 828 127 669 496 960 178 612 108 978 278 369 638 1333 535 976 73 903 539 1380 99 295 347 1182 491 872 545 1329 574 1418 412 1211 223 936 169 196 625 687 884 1290 1188 1302 921 1158 847 1212 657 1001 1110 1198 137 660 965 1069 265 932 98 1248 102 1213 39 536 18 1250 234 599 594 1397 861 1187 590 1202 79 818 278 1021 367 464 8 740 1005 1160 119 1274 323 760 903 1215 1093 1347 736 1360 560 1429 81 888 787 1178 712 985 229 1120 142 1073 345 549 404 1052 841 1153 368 …
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: 559 300 36 441 427 557 234 295 43 61 259 538 400 512 111 317 310 466 10 317 120 320 65 437 65 122 120 257 296 452 38 353 6 261 54 394 417 438 174 325 140 318 212 286 311 388 50 145 194 420 289 485 168 523 94 143 172 348 504 528 92 179 296 433 76 257 41 555 303 495 268 399 68 156 13 254 234 470 153 194 231 459 173 302 107 289 416 434 110 539 95 335 100 430 169 369 139 361 95 368 311 514 226 447 75 147 66 386 187 233 47 478 93 224 220 294 95 361 192 444 105 215 246 263 258 502 103 460 99 541 66 88 442 469 87 510 28 197 197 202 384 500 82 272 55 553 192 303 114 312 122 447 535 558 34 510 338 385 181 351 106 174 192 220 142 387 65 255 362 450 322 553 248 400 214 330 252 537 6 446 36 190 257 470 33 299 21 394 49 98 398 490 132 337 221 231 67 553 231 469 218 224 37 389 33 448 145 277 84 428 219 …
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: 763 1430 133 487 488 582 385 544 252 420 659 697 65 161 281 604 438 670 67 652 286 309 17 348 612 640 40 745 40 432 257 563 160 744 127 521 111 722 8 321 482 565 235 711 134 734 254 673 97 388 73 505 493 687 65 252 239 266 543 682 374 700 521 637 76 690 262 621 192 650 423 650 598 745 274 556 110 365 285 288 175 216 241 486 161 405 3 347 182 437 88 244 274 673 7 366 56 449 123 579 67 124 82 592 183 569 335 672 237 363 159 389 401 661 502 622 247 601 140 192 86 272 179 731 178 709 242 693 208 643 21 419 438 713 487 623 152 667 235 523 275 330 18 204 191 621 345 604 136 649 400 429 475 601 361 734 68 497 605 615 334 510 148 232 295 488 374 657 129 465 298 621 74 233 52 141 104 376 315 468 582 725 300 305 11 38 462 639 156 528 79 121 70 364 198 205 331 560 550 633 351 707 319 493 647 698 74 1…
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 <= 1861; 0 <= m <= 1861.

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