CT37412

Parth Counts the corridors

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Parth found an old ledger of corridors in the gallery attic at the trading post of Goldmeadow. The margin notes pose a precise question. 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 <= 2627; 0 <= m <= 2627.

Example 1:

Input: 1309 1174 316 1022 290 673 134 706 887 1160 190 207 668 1228 418 771 785 1054 968 1268 160 771 223 1168 158 895 21 745 422 589 1065 1217 509 847 696 1289 701 1208 419 732 1117 1276 93 1194 69 452 698 848 21 176 534 895 98 109 1087 1282 1088 1233 431 1118 928 1189 172 363 67 1049 1029 1158 194 1121 743 959 652 906 35 907 388 1087 184 485 6 105 211 393 552 1133 145 240 879 902 102 1120 484 747 205 220 307 548 807 955 288 993 681 1191 676 1021 256 518 30 577 202 1145 782 970 53 186 403 675 800 945 1151 1243 609 1143 67 695 207 270 1015 1257 226 540 100 1155 212 1075 600 810 759 833 524 1124 249 385 280 707 921 1111 899 1153 780 1303 592 801 255 980 506 1244 421 514 426 711 745 914 536 1219 396 1234 1224 1275 505 1007 1145 1176 787 803 192 566 717 898 12 303 509 1110 14 834 287 894 144 746 684…
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: 693 1536 347 691 225 629 240 678 215 494 15 443 17 657 146 331 469 574 39 350 225 479 201 660 207 512 130 186 68 263 240 327 581 588 421 564 63 464 32 332 53 555 447 471 376 417 196 239 393 684 218 423 37 235 91 169 324 364 480 623 246 521 11 35 122 328 1 273 136 156 54 457 23 235 180 459 217 680 453 575 135 175 340 672 334 369 135 623 604 654 488 550 439 480 275 484 266 283 323 581 358 560 19 47 475 608 113 177 133 226 579 675 306 504 153 208 439 622 221 638 184 452 117 482 451 601 476 490 157 243 296 666 280 627 254 410 82 344 17 50 422 517 12 343 70 670 315 479 185 230 63 631 222 533 127 624 204 599 305 539 321 469 289 334 217 250 209 506 130 456 397 545 153 595 664 688 151 526 466 692 599 685 9 118 567 623 376 481 625 674 194 552 29 685 49 143 375 407 363 529 59 558 552 612 25 412 208 …
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: 529 1499 373 405 37 193 267 317 33 512 31 204 205 304 98 135 192 389 21 270 102 494 236 293 16 414 223 460 217 373 124 249 208 226 196 260 39 314 225 243 176 417 210 447 154 298 67 97 272 318 201 488 290 504 79 363 36 310 60 366 199 211 53 345 151 447 146 189 172 394 245 252 204 279 123 286 254 333 171 400 127 451 6 435 114 144 91 374 113 472 91 506 6 449 29 246 306 364 12 139 201 279 98 525 66 458 443 505 96 521 273 402 487 502 113 448 222 251 88 466 231 460 1 437 233 392 414 455 360 426 201 342 345 410 118 346 111 232 6 369 469 521 273 485 76 228 266 478 456 502 426 437 89 425 123 137 318 489 43 261 40 422 251 389 53 329 480 522 83 127 133 202 290 485 51 177 79 107 179 266 309 423 16 29 218 350 15 362 304 398 127 222 427 444 102 164 190 426 364 396 197 419 183 344 161 202 174 391 48 111 …
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 <= 2627; 0 <= m <= 2627.

Loading...
Test Cases:No test cases
No test cases available.
Parth Counts the corridors - MEDIUM Coding Problem | CodeTikki