CT44980

The Build Order Beneath Caravanrest

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the dune sea of Caravanrest, Hope studies rows of roads entries. One clean number will settle the guild's oldest argument. 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 <= 3222; 0 <= m <= 3222.

Example 1:

Input: 3162 616 2929 2979 1003 1494 9 1405 679 2141 554 1634 1274 2027 1793 2429 237 387 150 2755 822 2433 510 1380 2322 2409 454 1424 1124 2483 2431 2988 988 1274 704 1454 1275 2834 2378 2489 511 1575 897 1513 1679 2623 119 2293 1396 2611 1211 1371 1118 2278 1162 2730 34 2765 162 917 1411 1549 1595 2864 647 706 2058 2492 139 1377 2250 2838 110 3109 318 2154 1752 2256 610 670 2133 2857 782 1328 451 582 764 2054 1207 3146 224 2729 1541 2224 201 487 2170 2847 1321 1465 1127 2547 11 2647 133 1174 1266 2436 307 684 494 2896 776 1279 1863 2759 274 2398 996 1366 929 1276 858 1286 2379 3156 576 1669 699 886 2897 3135 23 2349 1710 3092 373 2809 527 1834 257 2255 1663 2600 969 2233 1522 2451 14 2367 632 765 419 904 1449 3044 1610 2833 690 1371 336 2414 204 408 2144 2860 2397 2886 2658 3069 125 591 986 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: 488 1585 18 402 46 279 54 144 126 261 53 251 134 202 473 484 132 256 84 380 61 324 121 423 88 201 77 390 219 477 404 418 119 292 50 109 355 399 117 130 94 449 79 154 364 458 126 422 73 194 437 443 37 144 33 378 203 228 223 478 282 392 102 418 248 398 52 418 338 446 38 438 59 63 350 357 57 141 4 137 163 444 131 352 343 369 41 269 26 333 3 142 148 260 185 424 27 293 75 457 321 472 100 262 108 312 145 163 48 242 256 274 251 346 133 310 19 376 60 444 65 467 93 296 247 361 121 267 40 338 238 242 109 352 28 326 100 225 302 382 281 447 174 227 399 424 358 362 88 336 65 142 117 446 15 376 206 292 112 151 197 391 153 202 218 334 401 451 132 186 192 239 337 339 193 451 192 356 81 100 197 362 185 273 264 480 92 422 423 429 71 347 113 326 37 41 170 344 11 436 261 459 119 184 397 419 10 462 68 103 128 …
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: 1637 3148 167 1479 1009 1222 418 872 290 640 687 1273 48 108 129 386 423 1281 58 174 395 676 1233 1337 682 1233 146 473 164 759 1057 1357 163 604 732 880 1061 1168 22 1426 189 614 597 1590 339 805 195 792 1182 1495 852 1335 678 1611 1519 1547 942 1170 285 414 892 1316 992 1206 631 1043 47 231 1089 1325 362 1514 467 1609 456 694 905 1354 665 1096 1089 1508 717 1048 300 860 22 1609 389 1269 1215 1398 6 734 526 1066 1279 1535 167 972 534 959 461 1393 288 782 294 478 1534 1557 913 1294 541 878 1074 1580 304 469 1442 1501 747 1125 1410 1626 143 1444 952 1240 379 398 46 601 130 262 55 986 492 923 29 391 761 1496 452 933 749 1619 772 1518 533 1347 1181 1495 386 1276 98 177 73 218 10 1551 533 933 587 1370 88 833 847 957 31 1372 567 1035 681 1602 9 276 611 1549 370 1604 1477 1611 3 229 380 907 712 …
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 <= 3222; 0 <= m <= 3222.

Loading...
Test Cases:No test cases
No test cases available.
The Build Order Beneath Caravanrest - MEDIUM Coding Problem | CodeTikki