CT35892

The roads Build Order Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Pia inherited the granary at the mulberry rows of Silkmead along with its curious bookkeeping system for roads. Time to make sense of it. 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 <= 1764; 0 <= m <= 1764.

Example 1:

Input: 1609 1052 232 1203 48 1384 103 1363 385 575 667 860 729 769 419 1076 1074 1467 232 363 699 1060 154 233 819 1609 873 1572 41 227 392 1364 509 880 29 1511 299 1577 221 481 368 809 530 1353 384 429 193 494 446 992 747 1540 244 389 605 885 426 502 456 922 423 834 318 853 945 1573 836 1224 55 467 510 1110 185 1418 629 1589 350 418 369 951 352 861 277 683 337 1356 764 1063 238 1429 543 1525 537 1599 320 1505 654 985 539 559 333 1469 186 1113 780 969 1218 1328 103 1167 518 936 38 345 1092 1186 382 842 973 1220 970 1594 1152 1391 324 1532 193 471 517 1468 1235 1440 424 881 810 1436 1122 1254 173 1097 885 1201 1098 1181 811 1488 1381 1420 1010 1328 1173 1463 14 1265 429 1463 580 966 521 616 1324 1490 314 1238 301 790 241 1239 577 1156 704 1007 200 1036 310 637 965 1441 948 1337 124 912 208 381 591…
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: 745 307 211 284 12 102 36 109 105 444 410 545 101 254 159 417 325 363 166 492 164 295 252 640 188 207 133 573 391 478 7 636 482 620 108 360 244 596 73 268 696 714 258 499 559 578 148 383 349 525 242 459 32 397 225 503 333 424 84 269 136 211 214 733 294 651 86 480 90 252 266 663 622 698 154 404 176 295 439 633 181 209 66 559 4 577 480 589 125 186 114 250 144 655 181 716 466 473 352 465 70 474 422 697 453 563 76 131 584 699 83 193 99 626 401 701 111 583 83 731 421 558 273 287 192 383 127 557 154 700 147 745 195 717 102 271 41 300 444 675 332 559 595 617 89 664 480 581 304 374 280 529 313 315 384 541 256 668 444 703 315 644 631 666 349 645 132 720 226 452 415 439 536 594 51 104 336 435 189 528 123 481 222 458 47 664 444 678 243 472 345 460 64 685 163 255 295 561 561 584 309 314 93 454 228 734…
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: 353 389 132 264 63 336 6 128 98 197 155 230 212 323 120 261 116 296 90 353 196 268 113 308 66 299 73 119 59 189 107 196 48 67 52 253 41 205 184 232 178 236 254 301 57 140 211 266 182 215 83 118 93 115 266 278 124 171 144 165 42 87 95 132 1 165 279 314 82 260 55 161 234 296 292 296 190 217 191 198 199 262 139 290 86 95 191 289 7 289 54 103 161 277 58 247 100 162 110 301 176 340 42 130 120 219 29 213 117 131 13 227 32 234 100 152 54 130 214 303 112 229 153 337 41 249 44 317 123 260 13 40 130 207 245 266 217 247 41 114 55 67 102 320 65 307 263 330 7 340 257 261 7 62 41 91 40 201 43 342 26 172 85 292 124 125 235 343 16 336 25 98 101 137 39 284 264 323 173 238 275 291 187 346 87 153 37 312 129 244 14 174 98 147 47 214 13 164 73 179 17 192 133 347 205 306 307 308 224 326 53 258 75 323 138 174 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 …

Constraints:

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

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