CT59781

Tanya's canals Build Order

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the mangrove channels of Rootwater close for winter, Tanya must finish the canals ledger - one figure at a time. 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 <= 1173; 0 <= m <= 1173.

Example 1:

Input: 494 1079 221 358 13 41 77 145 274 407 458 465 32 323 265 388 393 418 187 351 173 274 34 168 62 293 126 228 276 452 316 324 14 18 55 314 93 367 361 456 226 404 336 413 55 452 223 474 85 359 75 103 215 300 207 220 154 322 180 263 129 403 356 480 139 377 105 129 112 300 160 405 198 272 420 437 169 267 86 494 94 264 101 345 396 418 132 220 383 390 218 384 113 326 124 170 163 399 157 463 403 479 296 423 322 470 17 93 115 132 52 54 208 325 17 475 221 485 175 253 216 438 24 382 57 447 204 440 437 476 21 239 123 477 50 304 86 143 240 311 335 368 280 417 98 492 74 375 357 483 208 299 287 393 6 169 8 218 366 441 44 213 250 290 249 377 199 330 24 135 105 205 317 420 197 388 64 283 84 211 98 363 85 219 14 463 153 457 116 347 417 439 257 416 314 398 93 450 269 466 126 159 81 218 366 429 175 251 380 472…
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: 284 1078 14 267 178 272 203 212 56 129 240 277 33 249 51 152 41 81 103 127 183 230 164 175 34 122 1 243 23 271 55 222 78 220 73 185 33 201 18 52 68 83 239 255 140 156 125 272 20 274 2 138 40 159 152 202 210 248 100 184 37 186 4 235 231 243 7 15 187 261 102 167 5 182 17 161 122 130 109 275 156 191 153 188 92 263 101 168 223 269 19 144 4 37 56 264 144 161 4 182 238 282 249 280 7 263 173 230 30 237 72 104 70 145 85 203 171 234 70 177 63 253 244 278 127 137 22 180 248 251 82 98 83 203 27 43 203 238 49 197 134 234 161 232 148 207 142 163 20 83 184 205 43 224 106 256 137 178 122 250 108 179 24 236 160 211 155 156 166 264 117 250 3 191 9 207 150 219 121 220 20 275 212 237 52 235 64 74 247 252 43 181 80 132 206 222 92 148 199 220 34 166 171 184 5 30 114 282 62 85 122 135 44 258 44 280 11 62 101 27…
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: 978 934 116 599 239 274 242 537 96 416 152 443 813 917 347 627 557 712 533 882 939 954 44 469 237 605 140 383 92 928 130 853 153 600 213 948 632 668 613 795 617 854 828 857 18 890 237 962 551 688 120 151 150 228 279 601 73 506 130 765 772 899 70 505 287 572 432 757 556 658 617 818 24 907 409 815 55 623 756 906 115 874 675 820 794 864 765 894 249 343 172 460 138 899 119 223 662 927 41 352 39 319 278 775 598 742 188 736 282 586 333 641 390 861 54 154 120 129 271 439 412 586 230 678 552 585 121 708 501 581 325 820 316 433 311 511 767 820 655 749 12 358 521 699 221 537 65 472 269 334 814 932 424 948 418 661 843 942 212 297 135 190 558 843 695 845 601 631 19 510 236 685 367 867 493 970 36 701 524 864 579 940 219 531 5 508 130 926 382 729 363 471 153 454 268 551 198 713 70 229 474 878 160 773 56…
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 <= 1173; 0 <= m <= 1173.

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