CT64870

Corwin's Roving Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the pine barrens of Needlepoint with crates of corridors, and Corwin the quartermaster must account for every last one. 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 <= 1956; 0 <= m <= 1956.

Example 1:

Input: 186 779 135 172 33 125 22 90 17 39 85 170 44 140 13 26 35 104 155 184 36 185 105 142 151 169 145 177 29 120 119 170 7 107 140 157 152 159 17 99 51 80 140 147 85 100 112 137 148 159 57 131 45 81 36 88 36 87 27 112 99 141 57 171 48 157 22 44 14 90 115 137 13 145 27 164 29 108 84 180 12 145 56 180 11 163 86 169 103 162 73 171 25 186 31 42 30 176 102 103 25 65 75 124 21 53 3 53 8 29 102 183 31 115 95 175 23 181 24 159 32 136 21 63 1 173 33 116 17 66 66 134 55 62 24 95 63 150 61 121 32 37 51 84 19 140 31 170 92 160 98 180 41 62 134 166 114 134 101 172 93 107 41 43 92 107 85 174 79 138 118 119 123 158 106 120 104 123 130 159 41 108 11 169 79 93 86 106 69 145 7 123 63 185 99 107 30 104 4 122 67 118 14 107 70 174 41 125 11 52 13 42 127 180 100 142 152 175 71 122 3 162 14 152 96 104 61 176 31 40 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

Example 2:

Input: 787 797 354 620 114 656 32 626 557 629 298 522 711 780 383 589 379 433 68 219 401 437 106 113 166 684 1 54 301 486 7 440 205 600 606 678 8 477 551 661 206 507 384 556 121 363 78 504 460 493 74 426 446 486 522 546 292 610 469 628 112 532 583 757 448 622 172 627 195 591 147 702 18 664 576 587 383 639 195 579 289 605 93 431 629 729 282 463 472 539 6 326 455 710 263 438 16 602 323 482 74 427 259 786 198 275 565 579 547 640 498 659 138 141 178 275 252 648 324 565 220 709 182 330 375 443 178 775 5 481 467 519 307 488 634 777 281 670 636 666 383 564 213 449 21 286 250 661 111 136 69 771 153 280 29 61 39 561 569 756 98 317 224 315 397 473 595 745 368 773 545 736 70 451 3 320 496 511 79 606 314 352 88 468 54 272 359 540 25 787 556 654 289 353 482 628 74 686 406 650 609 725 177 534 240 391 236 558 5…
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: 1899 1086 961 1270 1154 1698 718 1535 351 1400 1010 1371 399 1834 283 810 773 1753 1571 1669 18 768 905 1704 122 397 515 719 164 1779 308 1060 1347 1791 1111 1494 322 713 547 1278 254 1217 125 819 341 1455 635 1818 25 387 354 990 1377 1476 485 1733 312 1859 417 1630 211 474 174 211 837 1548 97 763 277 353 693 742 497 1234 1698 1884 355 1407 1333 1691 1261 1282 1094 1753 479 1317 867 1606 1413 1490 964 1250 734 1643 6 940 1279 1441 536 1458 826 841 250 499 290 385 455 1706 916 1820 784 1604 1074 1317 224 1164 153 1822 1248 1750 1615 1896 513 1168 363 1027 411 735 1389 1858 234 547 347 1139 431 457 85 562 1163 1451 445 1448 299 866 640 1699 944 1324 385 1861 1561 1747 371 723 428 1124 450 835 488 568 210 1761 214 400 45 1304 329 1643 75 1553 383 776 1152 1755 1016 1775 1625 1779 1182 1787 57…
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 <= 1956; 0 <= m <= 1956.

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