CT39648

Xavi's Wistful tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the archive halls of Scrollkeep, someone must prepare the winter inventory. This year the task falls to Xavi, armed only with the tunnels 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 <= 2979; 0 <= m <= 2979.

Example 1:

Input: 2945 2692 164 1472 41 716 1236 2002 1017 1584 480 691 1365 1758 1981 2802 621 709 1491 1731 277 992 1069 1112 715 1253 2003 2908 2554 2879 371 2368 182 1358 1529 1992 559 1920 1153 1705 2572 2632 557 2057 828 2481 441 2256 1166 1840 326 1938 258 728 321 393 140 795 752 2594 390 2211 1441 1614 315 1036 1061 2052 383 2849 387 875 1255 1415 910 1556 278 1426 69 935 390 2561 2420 2926 1869 2389 1708 2247 7 2401 2092 2338 389 1543 651 1299 568 2271 1897 2757 185 2051 1337 1651 503 2834 91 200 1431 1866 445 2796 228 742 968 1899 2295 2804 1969 2869 246 1318 240 1591 602 1821 1629 2314 2382 2663 1631 2426 309 1587 2206 2648 179 2927 340 769 1095 1252 546 654 1853 2199 310 2436 1795 2222 707 2502 966 1811 290 1524 54 2734 1247 1586 1288 1861 979 2192 660 1165 556 2839 1719 2648 361 1275 2246 2393 …
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: 2003 482 519 1992 537 1084 1158 1651 1000 1137 1625 1721 42 911 916 1493 1725 1885 37 1450 1509 1629 1289 1985 892 1559 1484 1664 373 1987 745 1443 689 820 767 792 424 1014 1046 1798 488 1155 229 1593 158 1008 52 1379 604 1335 335 1465 858 1350 91 256 37 1999 229 1825 171 556 1219 1350 1080 1830 201 1873 306 1741 1917 1977 220 1455 1535 1694 862 1057 1729 1784 807 1320 906 950 575 1291 682 924 821 1119 1454 1587 23 104 885 1166 83 1373 160 730 320 835 422 1059 751 1520 354 1136 744 1913 49 1246 1300 1332 21 1630 520 1683 1108 1899 764 1793 101 642 256 1797 667 1479 291 1890 787 1302 290 1631 60 1705 329 1511 18 1375 878 1316 226 307 45 1683 591 1346 1561 1997 1570 1620 264 1880 1135 1232 240 541 427 1371 738 1377 131 897 117 300 74 1688 211 740 741 1384 422 1502 51 453 542 1343 309 1997 12…
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: 1183 422 516 753 77 426 679 753 233 497 626 759 147 928 167 212 416 469 559 575 542 1117 836 954 380 644 661 920 237 267 764 769 1011 1087 264 1106 864 1007 860 1011 495 686 667 890 327 1030 123 514 521 571 3 922 679 1136 81 98 651 693 850 1134 275 992 135 288 503 765 624 939 1130 1158 37 629 564 787 295 683 145 897 487 852 12 28 342 577 205 617 987 1131 343 686 126 955 520 654 973 1172 737 776 284 689 657 805 404 817 348 1100 383 861 258 745 136 612 258 942 364 925 53 314 128 646 970 1077 156 1074 251 788 433 594 109 339 197 1056 159 173 403 589 181 542 160 1023 1071 1104 987 994 156 278 482 764 180 927 249 904 297 1012 259 261 352 675 378 634 367 938 230 510 475 896 295 935 291 576 234 326 141 581 617 1130 66 251 814 1070 596 640 567 1161 233 682 676 926 376 754 381 893 803 1003 817 845 …
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 <= 2979; 0 <= m <= 2979.

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