CT65010

Last corridors of Archivist

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the crane marshes of Stillwater opens only for a perfect tally of corridors. Archivist means to find out. 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 <= 2002; 0 <= m <= 2002.

Example 1:

Input: 1178 791 763 954 267 892 725 742 743 826 13 451 76 127 310 599 635 722 22 807 673 797 71 629 232 801 1020 1101 453 627 55 254 545 1137 333 610 454 821 424 789 150 1008 10 469 597 1069 348 355 736 1073 512 1045 358 593 640 1077 157 864 879 962 920 1110 462 857 418 677 212 1175 864 1165 684 873 512 912 140 424 975 1002 184 844 707 837 278 411 176 680 330 1119 923 1030 138 282 885 985 685 1049 620 1068 72 669 693 1151 886 1099 525 976 138 1011 94 1071 968 1147 353 781 424 755 953 1113 142 980 432 994 103 810 320 624 648 1117 587 763 36 506 16 1100 148 180 779 1136 549 653 15 396 528 838 119 358 465 1060 289 1063 319 754 130 324 541 947 576 608 767 857 427 930 346 973 600 773 521 570 590 983 466 788 154 187 270 979 616 643 717 1176 570 1087 114 1112 230 1077 26 104 200 1153 107 576 202 655 136…
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: 1144 1510 194 481 28 49 280 539 22 176 139 246 309 675 518 938 428 693 356 972 64 934 515 871 392 484 273 839 485 949 902 1089 402 423 570 1079 25 251 198 1035 141 742 597 703 163 1052 358 692 757 1120 313 525 357 1002 148 1092 428 583 144 629 247 877 741 754 352 530 593 828 904 1061 296 932 490 1045 311 563 385 637 642 698 510 715 281 614 940 1104 41 874 759 945 60 496 90 885 530 1118 454 694 193 747 263 745 328 792 758 1094 468 488 634 1003 819 849 413 742 537 1130 127 339 205 626 252 1133 194 924 364 764 311 611 345 598 333 856 272 858 258 672 137 166 404 1120 195 320 647 680 48 474 289 1120 357 953 543 711 626 659 627 793 393 595 258 702 29 100 23 334 266 362 656 888 120 1105 750 999 320 1107 163 628 350 894 263 771 470 541 125 253 474 887 421 756 79 907 53 261 381 403 605 975 272 649 …
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: 593 110 195 373 173 471 48 534 199 529 107 560 413 556 1 443 402 471 21 534 171 581 77 328 541 568 28 526 468 517 16 247 240 387 481 532 147 298 271 362 186 241 153 500 81 492 360 486 170 429 38 214 199 578 529 536 508 524 15 491 201 298 327 530 405 446 52 58 337 475 166 271 81 446 485 511 56 81 224 574 42 103 503 560 534 562 474 585 77 334 532 587 40 281 92 479 506 583 430 473 316 515 11 146 201 362 106 539 58 331 189 331 342 531 4 448 151 319 156 510 68 487 373 426 61 172 432 459 60 305 251 540 460 531 52 321 80 136 226 410 8 58 273 385 223 448 252 342 161 222 114 173 326 373 96 548 92 214 503 520 404 580 267 550 55 299 344 563 129 192 381 541 194 249 66 344 63 367 275 372 200 247 295 530 74 477 362 534 229 332 124 367 156 237 161 249 315 338 154 274 166 352 40 398 493 582 23 478 110 467…
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 <= 2002; 0 <= m <= 2002.

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