CT58347

The bridges at Prismhaven

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Lakshya runs the lighthouse at the glass towers of Prismhaven. Today the books show a list of bridges, and the numbers must be worked out before sundown. 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 <= 1601; 0 <= m <= 1601.

Example 1:

Input: 422 1087 52 367 143 184 67 221 230 353 177 218 141 314 2 30 355 419 56 192 99 414 301 361 187 419 173 411 201 364 87 118 273 320 91 255 214 385 210 238 88 268 83 110 168 381 81 289 209 379 251 345 95 202 199 221 100 219 104 189 40 171 120 262 266 349 59 256 119 265 85 356 161 171 67 367 319 329 50 124 117 208 60 240 93 411 86 421 50 276 289 374 386 399 42 60 111 136 92 111 186 388 346 420 22 291 166 371 38 420 122 411 69 422 220 343 39 93 262 330 146 266 239 302 99 276 242 299 33 113 209 414 239 293 130 215 52 128 273 315 174 327 25 393 25 69 21 45 104 177 175 212 72 387 187 314 127 370 109 177 386 407 141 270 284 329 303 330 216 337 28 177 115 172 272 415 171 397 290 304 418 422 282 353 299 360 26 315 141 321 250 305 199 388 128 220 1 22 79 374 253 410 9 175 49 414 109 229 35 271 140 205 …
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: 956 778 84 903 263 849 563 625 684 710 646 686 69 620 120 718 414 430 388 617 526 625 387 589 254 892 71 376 28 231 84 560 314 698 59 685 34 615 247 919 182 517 535 686 744 892 45 646 223 739 534 896 297 930 631 849 435 927 18 464 150 873 40 918 789 793 83 454 297 867 82 151 857 869 538 905 27 396 286 443 397 898 331 411 94 213 156 520 843 847 225 468 134 211 142 535 609 654 710 879 121 600 508 837 647 867 573 847 592 881 205 933 123 364 25 290 266 894 241 390 183 406 535 548 91 569 206 575 722 946 305 834 552 852 240 557 371 820 50 104 291 679 253 407 476 913 453 756 226 501 505 843 679 681 372 799 856 880 218 774 336 417 716 816 563 894 472 896 436 651 658 797 268 683 81 288 51 583 132 836 395 840 629 768 298 883 18 775 209 220 89 161 664 904 804 838 579 819 296 448 410 693 434 921 191 7…
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 132 211 374 205 283 82 155 194 265 145 375 248 298 114 280 233 330 66 210 86 323 145 236 62 187 180 250 44 55 277 353 99 243 36 87 37 256 137 217 142 371 283 295 166 187 17 348 38 305 106 312 35 363 18 245 23 265 222 308 23 145 186 333 140 192 27 374 205 326 217 301 214 305 9 193 65 111 149 185 240 360 78 185 275 327 128 346 95 325 290 362 364 369 131 343 158 333 128 305 211 369 15 70 91 99 64 109 88 214 130 187 68 152 5 50 288 369 349 353 216 256 123 173 74 218 49 375 21 162 9 229 107 374 29 317 21 85 141 235 207 286 93 280 235 239 45 162 109 147 74 336 309 345 128 179 9 273 71 97 95 363 22 110 279 302 3 77 207 341 5 290 64 126 159 208 214 335 200 346 92 205 43 199 25 311 173 352 154 215 149 224 2 189 155 310 21 169 216 233 204 307 75 297 253 283 5 195 109 295 102 348 311 370 216 360 …
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 <= 1601; 0 <= m <= 1601.

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