CT57535

The roads Build Order Puzzle

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the old quarter of Brasshaven, Nils 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 <= 2520; 0 <= m <= 2520.

Example 1:

Input: 959 2233 120 565 568 911 569 683 709 932 363 783 395 772 442 950 780 947 49 181 510 548 687 887 175 832 116 351 264 915 375 862 771 828 291 926 236 907 35 336 268 738 394 598 769 869 544 552 327 852 871 881 150 649 34 203 38 51 460 946 741 934 96 284 352 455 204 580 45 942 515 658 196 216 511 551 626 923 256 647 625 696 248 467 49 787 107 120 557 693 412 697 284 937 201 611 263 738 633 949 89 255 51 729 466 720 189 810 518 662 115 492 52 519 166 407 257 594 33 510 347 908 59 267 290 416 163 725 433 949 241 505 396 540 117 747 428 948 68 488 232 553 246 841 723 924 526 858 597 733 235 782 225 370 391 857 20 850 630 736 755 885 537 577 741 917 167 188 121 748 868 948 726 877 771 786 430 659 675 928 169 438 117 949 602 804 321 424 320 919 580 663 18 447 53 379 318 428 333 785 622 900 27 43 64…
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: 425 1747 9 293 272 387 102 231 171 410 41 155 378 389 81 252 135 349 319 356 105 239 23 245 142 218 69 425 302 342 27 263 67 263 93 255 79 225 58 158 114 282 147 329 140 149 247 296 14 269 153 157 381 402 113 419 210 251 247 380 243 353 106 348 47 328 107 399 136 216 85 408 141 357 94 212 76 362 123 317 15 84 91 204 45 59 122 261 47 249 195 368 21 129 88 141 189 249 134 253 87 216 159 303 293 353 329 399 28 186 298 339 97 260 202 357 14 197 322 397 274 341 49 176 32 226 35 107 143 328 197 319 114 341 57 166 114 129 308 357 281 408 62 259 316 380 198 412 68 137 15 269 216 225 83 420 59 313 375 383 108 282 25 388 103 396 67 329 123 268 196 334 77 275 40 156 224 253 96 111 74 336 206 213 59 409 298 300 136 323 341 345 124 301 198 258 126 246 87 284 138 206 373 402 390 397 130 271 66 176 107 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: 2199 1351 1476 1532 843 1519 1210 1973 676 770 384 694 1113 1291 826 2113 1232 2194 522 821 1382 1533 558 1380 548 585 1013 1507 1125 1921 1129 2145 107 523 32 59 811 2062 1054 1110 556 877 845 1958 763 1824 841 1460 1148 1903 496 715 1924 2116 505 2173 309 1738 466 1575 984 1179 928 1410 1021 1497 1397 1906 622 1515 256 2149 575 2120 6 510 90 743 1106 1702 1004 1047 336 1214 668 1331 1435 1682 1250 1680 877 2164 651 1870 1109 1634 145 1646 406 1710 1405 1448 246 1111 1028 1970 334 1124 1211 2049 626 1562 1186 2045 1431 1735 332 1328 542 717 894 907 346 1882 840 1603 2055 2069 937 2195 675 921 1516 2199 1721 1874 567 877 649 896 661 2118 825 1024 1023 1510 1217 1679 363 1756 1838 2149 115 1000 192 1058 135 469 544 1696 1801 2198 1894 2047 672 920 746 833 516 2136 754 882 87 344 1109 1157 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 <= 2520; 0 <= m <= 2520.

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