CT47204

Theron and the Sunlit routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Theron found an old ledger of routes in the timber yard attic at the quays of Driftwood. The margin notes pose a precise question. 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 <= 3954; 0 <= m <= 3954.

Example 1:

Input: 1917 2463 264 794 450 611 138 1744 696 1915 70 1044 935 1754 375 1317 335 856 804 1515 149 1302 89 1227 856 893 651 794 28 36 252 1308 748 1484 647 1465 643 691 131 885 90 329 1474 1784 769 1422 327 938 811 905 649 1016 586 982 1384 1854 540 1670 747 1876 1718 1723 57 1744 601 1219 726 1490 240 615 965 1506 749 1158 23 207 504 1631 339 1448 620 893 58 1601 367 1894 779 1823 593 1120 205 1222 618 755 221 887 606 1469 540 1417 439 1380 360 760 116 1424 850 1314 348 1133 700 1168 1022 1335 1422 1651 273 1605 157 1857 247 1080 309 322 1788 1798 120 849 1093 1219 153 1594 292 1726 550 1006 579 1871 448 1361 1095 1698 219 1566 402 1686 125 684 69 874 605 896 1264 1351 419 1625 1141 1685 1443 1512 441 649 912 1123 493 1093 8 958 550 1307 663 1501 722 1390 1108 1412 1004 1608 275 829 1080 1232 231…
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: 1540 196 574 1386 924 1251 796 1385 54 801 173 511 941 1044 620 622 70 1516 437 510 214 1111 509 1049 665 1224 206 881 512 1445 729 1120 938 1205 639 1066 511 566 186 213 275 1263 424 1121 751 1234 83 469 373 1054 198 842 171 1203 114 1041 362 1157 64 139 562 1452 488 1350 569 632 410 951 1101 1427 375 668 662 1248 33 42 1263 1410 697 1473 395 396 95 862 1245 1378 1022 1269 205 782 193 1070 74 1448 103 1024 124 572 511 694 80 567 606 1368 554 591 133 910 173 1032 639 1317 1176 1461 712 1316 1136 1524 345 1192 946 981 278 612 386 848 35 930 374 921 606 1053 520 525 222 573 110 464 43 918 430 813 328 1278 525 584 499 730 879 1537 423 696 24 505 540 815 1088 1502 151 161 282 1022 302 364 517 1018 93 635 906 1073 502 712 564 946 44 1524 175 1244 376 1233 684 755 740 1157 797 1238 577 768 974 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 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: 1506 2739 410 446 446 1217 652 1431 710 1408 612 1021 136 1355 89 744 328 1173 1073 1128 1180 1325 12 933 260 399 1387 1403 624 1413 830 1356 841 1438 662 1502 669 1499 602 992 486 1165 712 792 660 1210 208 420 373 1173 366 1453 1190 1237 276 1095 72 1317 410 1400 260 554 166 1165 49 1399 504 1312 532 1169 536 1342 69 1322 447 978 330 1232 250 837 217 1430 404 958 841 1002 646 1419 382 864 732 1384 727 740 5 229 706 1203 121 1469 510 713 301 806 1484 1498 794 1196 847 1338 1219 1343 99 1335 234 527 499 1175 252 589 1019 1157 228 420 1214 1367 554 1029 818 957 425 1093 18 1103 308 688 1045 1350 11 73 562 1109 202 520 805 1127 962 1432 230 298 36 430 999 1413 619 808 105 522 19 1218 343 1329 1202 1259 564 1472 514 1109 1164 1473 1228 1418 650 872 181 1257 512 749 159 188 127 1141 295 1306 38…
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 <= 3954; 0 <= m <= 3954.

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