CT48778

Ysolde and the Solar tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the valley of Misthollow. Ysolde spreads the tunnels records across the table and picks up a sharp pencil. 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 <= 2191; 0 <= m <= 2191.

Example 1:

Input: 1035 1079 219 263 72 986 280 918 696 912 123 418 319 489 373 807 142 641 604 930 302 617 104 308 198 505 136 975 923 929 358 821 288 543 169 444 109 324 185 312 442 951 126 952 595 728 220 941 339 932 359 734 276 594 270 533 256 754 167 922 496 1011 355 499 427 558 749 796 888 897 485 933 132 902 286 823 172 758 282 292 463 1013 577 813 118 746 156 964 57 789 415 418 59 273 52 374 145 611 123 999 581 742 370 912 565 742 44 937 746 831 485 1009 695 1001 127 512 554 669 495 664 580 639 253 698 709 947 765 982 79 514 90 542 81 658 288 627 107 418 20 360 254 265 413 666 440 595 84 896 703 924 369 566 512 992 770 913 140 438 88 1009 468 595 409 528 6 160 467 869 621 818 586 1001 752 845 553 878 122 971 48 194 510 815 424 603 352 592 594 853 81 379 271 841 798 874 114 733 48 733 74 374 210 637 4…
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: 2012 1332 1247 1709 682 1404 156 893 874 1883 1053 1664 665 1205 338 870 67 1020 881 1975 1942 2008 1244 2000 888 1929 1774 1854 378 1656 685 1802 1140 1294 1525 1929 1258 1383 1302 1357 902 1908 82 223 1066 1145 641 958 786 1991 139 1590 1070 1599 142 1634 712 1745 62 1334 643 2006 168 1542 906 1818 620 1451 57 1905 1042 1740 428 880 829 1604 360 1675 1787 1927 312 908 797 910 1184 1928 424 1509 566 942 229 680 619 1149 216 258 904 1416 178 1152 1038 1547 493 664 603 768 61 573 139 1856 604 1497 1634 2003 521 1464 1125 1919 1082 1981 863 1022 203 686 143 1234 698 1143 370 931 913 1353 115 1246 641 1996 1708 1909 641 1222 1612 1972 1294 1698 43 1377 1489 1985 931 1725 1887 1940 779 1981 1390 1497 641 1348 150 419 236 1998 323 1660 368 421 764 1699 815 1466 58 439 253 1153 1402 1811 205 174…
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: 1731 942 235 439 36 1067 629 1709 808 1161 658 1559 174 1315 623 1130 1247 1492 773 1592 801 1196 33 1600 365 407 863 1068 825 1145 57 209 514 1055 44 689 625 1182 294 553 1576 1668 461 1659 445 1596 675 1641 490 788 1233 1288 266 759 315 813 1396 1595 283 1526 261 1283 190 601 430 725 255 366 613 697 622 1593 546 1677 144 1446 707 1462 917 1360 300 1154 876 1156 1002 1455 520 907 143 824 71 1195 538 1137 588 751 229 1034 577 1192 135 1461 916 1675 698 768 860 1383 202 1191 436 820 222 566 242 253 319 1720 23 819 345 1401 438 1447 268 310 379 549 55 718 79 331 1366 1375 445 1178 72 181 613 1123 475 1397 582 1108 343 831 184 1038 851 1532 678 1349 671 1324 71 1281 1185 1266 583 1523 64 93 509 1470 57 1142 1252 1692 22 1543 87 978 44 1593 504 1482 497 1493 441 691 333 1183 634 1716 289 1673 …
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 <= 2191; 0 <= m <= 2191.

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