CT39378

The Ancient canals of Clerk

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the crane marshes of Stillwater, someone must chart the migration season. This year the task falls to Clerk, armed only with the canals 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 <= 2342; 0 <= m <= 2342.

Example 1:

Input: 1975 280 1787 1880 722 800 492 1003 1044 1698 219 326 613 1451 644 1723 1339 1973 288 1910 1231 1841 786 937 912 1866 45 1616 6 1306 978 1865 703 780 1049 1952 1197 1724 1174 1388 690 1813 155 1806 528 1811 798 1578 461 1879 595 1549 1650 1812 309 1056 973 1099 114 1116 522 1131 312 1266 53 1263 314 1219 640 881 1266 1642 370 839 200 1699 303 445 1115 1557 1556 1807 609 1412 722 1137 301 1069 833 1213 789 1236 520 769 388 1934 1261 1340 77 1210 204 636 830 1271 663 1537 492 1713 1127 1556 528 633 327 1937 180 1717 13 673 86 1362 811 1044 408 1287 1044 1725 849 1615 78 1207 181 864 377 1779 703 1496 751 1004 191 1139 787 1491 1640 1772 1651 1870 1772 1861 1749 1945 1738 1758 1768 1929 1471 1934 61 543 28 387 8 1052 22 1487 276 1716 210 936 195 1402 749 1091 785 969 132 1841 395 1343 973 125…
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: 690 2277 177 293 476 509 302 647 557 631 50 192 427 631 609 631 253 471 3 341 200 589 243 583 297 340 122 246 273 358 347 552 355 637 170 494 352 639 214 516 112 157 130 149 654 682 349 444 107 131 331 651 148 275 532 673 150 604 430 570 123 519 17 428 133 315 157 171 543 573 295 369 212 422 69 74 83 203 138 658 156 674 171 534 15 661 63 229 538 690 164 181 28 97 164 615 22 39 292 687 67 406 308 375 104 159 292 644 206 411 268 328 525 590 131 426 120 187 193 611 311 542 36 483 70 178 261 370 186 313 472 507 149 373 170 666 432 565 240 312 68 657 336 375 311 557 460 665 183 432 159 196 383 408 161 462 16 610 124 269 81 436 30 655 70 78 256 358 144 513 302 483 429 629 53 357 210 467 202 261 456 463 65 435 138 202 601 668 7 391 142 669 230 599 365 370 42 435 277 310 142 583 570 671 109 364 16…
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: 1745 735 225 931 9 914 315 1455 893 1071 793 1668 196 1354 16 1198 136 477 71 1415 1294 1401 800 1336 333 1742 130 1183 914 1446 623 1400 608 1517 433 464 258 491 1447 1682 301 1268 268 1435 363 593 1371 1449 1312 1553 1147 1486 398 551 367 386 666 1010 912 1494 569 1096 1627 1686 168 733 247 1691 907 1379 223 1555 533 1272 1251 1666 193 1521 601 1137 1084 1288 348 612 70 1441 715 1622 710 1636 696 1439 401 464 206 1334 423 851 228 1339 747 1292 850 1060 1075 1543 416 1150 948 1329 626 888 1154 1588 1187 1536 270 457 42 795 1151 1662 1321 1685 490 1487 549 1243 662 1153 483 1268 258 437 55 726 707 897 214 1392 339 1051 433 1078 804 1326 272 1152 1389 1684 387 1202 162 1378 571 1538 628 847 1282 1504 1003 1741 784 1185 834 1475 987 1382 1185 1743 98 1008 148 1655 1403 1560 545 772 1236 1532…
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 <= 2342; 0 <= m <= 2342.

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