CT42807

The Build Order of the Ruby tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the gull cliffs of Screech Point as Scribe unrolls the day's manifest of tunnels. The tally will decide the next shipment. 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 <= 3660; 0 <= m <= 3660.

Example 1:

Input: 1082 3209 139 812 1 551 766 946 792 801 478 768 610 947 438 994 343 449 83 288 110 479 317 432 437 760 25 280 388 1004 121 1049 31 251 494 644 21 859 69 906 398 601 716 804 613 767 18 192 162 602 373 415 146 837 781 969 64 772 19 329 171 800 286 752 337 593 160 596 47 775 164 464 448 513 440 728 96 472 342 566 69 381 197 644 433 1026 494 854 330 926 258 961 44 622 390 863 374 796 683 834 237 296 205 396 622 726 585 810 260 1002 329 844 206 538 336 429 183 364 642 860 72 616 552 581 132 876 163 488 81 506 127 334 412 876 869 877 115 183 518 866 14 286 262 1031 231 864 476 659 71 521 101 975 34 78 106 167 689 930 377 1063 794 801 619 716 207 1019 808 938 125 992 414 982 142 160 169 861 588 960 229 972 169 319 714 824 491 825 771 1082 252 433 39 826 1052 1064 474 831 217 586 394 717 44 288 15…
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: 1834 3408 170 1632 1306 1373 570 1370 679 1779 925 946 1140 1596 634 1575 898 1429 395 706 684 1233 893 1257 487 1509 734 1557 423 1008 210 750 234 1193 66 1125 729 1157 858 1573 653 1489 203 1133 951 1816 242 1125 988 1056 1258 1440 43 1348 1001 1420 619 644 281 639 815 951 305 532 469 1475 358 1591 1079 1436 385 1247 311 1832 50 962 394 780 724 940 1311 1412 250 1415 298 1377 1051 1513 898 1085 22 85 784 1528 428 533 533 1645 212 1394 845 1592 101 1207 547 1522 1578 1737 46 942 1308 1327 1116 1670 936 959 1253 1361 187 878 594 892 1087 1484 1736 1817 646 1219 1060 1212 830 1111 1108 1177 65 1064 712 920 1429 1484 1547 1752 277 1105 251 720 333 1624 575 1436 1204 1497 359 1582 1174 1768 381 666 572 1512 1479 1716 815 919 386 1516 867 1030 984 1086 613 1550 1251 1260 1321 1624 643 912 1276…
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: 1602 1300 663 1387 629 658 1030 1491 58 1004 579 1427 58 881 770 837 1162 1244 372 801 798 1243 1046 1106 1235 1291 506 637 625 1033 362 818 66 492 342 416 642 1298 831 908 729 1180 590 1236 266 734 112 1580 3 1029 373 682 193 1158 76 252 831 1331 111 189 183 245 1419 1563 437 1072 552 665 878 1322 370 1278 87 562 680 849 106 423 729 1167 665 1502 109 1415 42 230 497 695 208 1537 389 1022 1015 1484 387 1373 1294 1302 343 1539 792 814 137 548 169 1480 359 1067 429 532 1345 1527 587 853 455 1089 238 1128 83 940 568 1486 120 1587 628 995 1367 1550 180 1051 1217 1467 572 637 533 1192 139 1120 1301 1355 59 1213 631 903 473 734 144 1465 209 985 643 969 1131 1395 338 1175 521 664 993 1440 904 1602 160 1229 777 1573 60 426 316 578 906 961 995 1402 52 1159 454 759 1207 1257 312 1222 521 1223 1252 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 …

Constraints:

1 <= n <= 3660; 0 <= m <= 3660.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order of the Ruby tunnels - MEDIUM Coding Problem | CodeTikki