CT40603

Parth's corridors Reckoning

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the clockwork quarter of Gearford with crates of corridors, and Parth the surveyor must account for every last one. 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 <= 1285; 0 <= m <= 1285.

Example 1:

Input: 1099 190 796 982 213 241 218 504 293 827 274 726 137 786 160 692 526 1095 143 330 120 655 943 970 108 714 572 836 317 578 806 1080 23 622 218 617 465 743 389 964 507 702 149 915 927 1068 44 937 90 628 181 1094 630 846 446 959 711 1043 389 653 94 395 205 833 121 528 418 807 504 759 507 749 230 415 527 620 211 738 577 786 641 740 502 753 169 948 131 951 500 528 486 694 421 456 159 744 774 924 487 1006 803 944 819 889 102 763 488 709 915 940 416 718 212 617 113 420 379 717 113 339 279 781 290 1037 191 703 679 803 659 1084 239 1029 59 715 857 863 86 127 172 868 697 862 312 916 295 410 121 308 881 1072 93 875 226 1059 367 1039 259 913 14 400 492 545 872 1024 9 309 489 1011 131 357 915 962 388 511 251 831 145 551 939 979 643 977 19 1049 187 325 239 811 545 905 649 986 475 772 38 858 629 668 76 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 2:

Input: 610 12 1 337 274 418 141 196 58 335 43 410 36 519 63 168 254 256 155 382 413 594 428 574 94 557
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: 376 267 33 277 235 369 260 321 13 82 109 157 202 293 263 309 70 251 11 109 39 338 73 175 82 305 169 327 142 320 9 72 89 260 129 260 144 309 249 290 181 224 240 334 248 270 113 213 1 215 115 263 81 267 19 258 203 261 79 93 98 135 92 104 192 260 82 199 214 327 169 332 245 279 125 189 97 213 230 298 34 373 147 174 131 372 31 66 32 67 340 355 9 171 46 264 49 345 180 353 216 288 5 69 19 63 5 53 147 164 150 278 62 72 123 286 264 331 9 293 62 245 9 137 124 357 206 283 42 70 110 230 62 324 117 295 114 253 318 364 126 358 20 249 16 346 349 359 227 351 152 185 92 141 132 374 125 342 17 168 48 173 120 273 172 194 64 146 175 350 240 357 171 320 195 333 192 312 81 97 190 295 19 168 3 259 53 302 232 295 162 369 84 326 252 326 161 292 132 259 135 278 106 111 9 343 160 279 231 347 174 309 10 145 196 292 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 <= 1285; 0 <= m <= 1285.

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