CT61722

The Build Order of the Polished roads

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Wren the reckoner watches over the maple sugarbush of Saprun's stores of roads. A careful computation stands between order and chaos. 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 <= 1828; 0 <= m <= 1828.

Example 1:

Input: 22 231 7 19 8 19 1 17 6 19 13 18 12 18 13 20 5 21 13 21 17 18 10 13 8 12 2 8 10 15 11 20 6 18 6 7 8 14 6 9 11 12 7 17 2 6 17 22 8 22 12 19 7 21 11 14 1 2 14 18 14 19 3 8 8 11 14 22 15 16 1 8 4 22 9 19 2 11 4 6 13 22 9 20 1 12 5 12 3 22 1 6 6 20 17 21 14 21 4 5 7 15 12 14 11 19 3 12 4 10 8 9 15 18 20 21 7 12 10 22 10 18 1 13 7 11 5 13 8 15 11 15 14 16 4 19 1 7 1 22 3 4 20 22 3 10 18 21 5 18 4 21 16 21 16 19 9 18 4 14 1 10 5 15 9 15 15 22 15 19 10 12 13 19 10 16 8 10 6 15 11 18 18 22 5 6 2 16 18 20 14 15 6 13 16 17 7 9 2 20 4 12 19 22 4 20 8 16 1 5 9 11 3 18 6 10 3 13 12 21 11 16 6 21 9 21 9 16 11 22 8 17 5 11 3 11 7 8 5 9 6 14 9 10 18 19 2 7 1 3 8 18 9 12 2 13 1 16 16 22 19 20 9 13 6 22 9 22 3 5 1 15 2 4 1 4 7 20 4 11 3 6 14 20 4 16 1 9 2 18 5 10 1 19 10 21 13 17 7 22 6 8 4 13 4 9 19 21 3 2…
Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Example 2:

Input: 913 757 169 255 283 455 719 827 141 372 682 733 702 833 222 298 77 737 549 698 478 488 30 39 64 323 425 717 224 607 259 451 622 631 618 746 264 781 154 766 24 553 219 277 462 589 235 837 67 159 149 687 667 900 36 194 21 252 266 585 802 900 25 866 421 704 75 758 101 276 384 611 217 819 830 888 730 885 420 763 474 499 166 646 446 633 366 668 259 395 232 261 9 667 51 586 132 710 92 456 619 889 23 74 156 769 137 726 33 283 612 705 501 590 68 320 165 659 771 866 58 669 207 826 274 812 752 817 14 677 406 514 177 426 197 206 60 831 330 675 155 588 125 145 434 892 811 903 597 648 136 835 659 836 74 794 4 525 180 772 570 663 171 648 381 764 144 500 72 92 482 850 107 859 344 750 176 591 99 548 342 690 660 911 8 513 171 520 68 464 250 656 453 895 12 731 67 194 647 760 158 885 272 342 331 682 259 801 …
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: 1497 1525 358 1431 434 619 158 872 1217 1476 932 1199 241 1042 810 1477 557 1073 35 717 758 1306 679 766 26 145 755 1156 673 1107 147 654 478 949 729 808 248 369 367 840 1053 1462 618 784 663 951 566 901 396 969 968 1452 378 717 328 1141 646 1034 1410 1423 732 1441 107 1467 460 929 324 370 226 589 609 1062 804 825 1009 1443 203 876 385 471 387 1057 191 1194 1224 1402 1392 1458 555 1438 506 1328 39 684 56 889 167 1475 1118 1219 297 1171 1285 1409 688 799 255 504 1382 1489 677 1140 1190 1338 768 1150 1005 1102 1290 1457 423 1487 27 1405 1245 1485 127 1089 233 789 210 1115 99 458 327 943 313 1178 120 610 79 325 620 928 231 618 241 747 649 724 1148 1443 73 969 662 946 328 1231 365 663 455 734 304 886 993 1491 181 485 693 1401 635 819 220 559 416 928 189 646 34 112 127 1323 654 1047 454 844 913…
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 <= 1828; 0 <= m <= 1828.

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