CT55193

Last bridges of Anaya

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Anaya found an old ledger of bridges in the exchange attic at the salt flats of Palemere. The margin notes pose a precise question. Task: Print the minimum number of edges on a path from s to t, or -1. Input format: First line: n m s t. Next m lines: u v. Output format: Print the BFS distance or -1. Constraints: 1 <= n <= 1199; 0 <= m <= 2398.

Example 1:

Input: 1057 2342 1 1057 164 891 127 469 451 722 26 220 9 57 152 917 19 302 332 582 174 825 622 1026 92 937 975 991 48 263 176 899 445 769 282 910 296 763 143 349 121 501 91 783 117 654 407 815 91 374 10 65 676 716 351 979 54 764 298 918 633 776 496 796 148 871 153 440 204 272 375 702 70 449 440 653 652 1054 177 185 575 589 57 208 1023 1046 644 810 442 448 310 639 174 641 75 787 345 683 587 967 412 591 984 1042 543 614 632 804 252 564 725 935 767 949 40 834 11 361 660 888 390 921 69 148 534 1016 341 358 676 973 118 676 182 771 485 547 15 279 221 756 521 989 554 800 368 698 97 820 282 660 390 621 175 456 331 959 807 814 250 563 317 453 318 860 194 927 269 1035 957 1023 460 1021 379 1018 397 532 440 495 31 796 88 965 91 638 412 414 266 778 790 869 232 404 376 1037 194 755 604 654 853 1044 162 882 30…
Output: 5

Example 2:

Input: 636 1024 1 636 196 631 472 513 446 596 468 560 204 564 280 404 268 404 254 558 150 210 112 132 119 209 141 149 7 443 4 349 80 161 39 551 189 348 115 167 17 157 23 492 477 596 435 488 133 622 19 49 36 350 115 477 552 613 481 606 148 385 288 467 290 385 23 320 123 210 374 557 460 476 249 412 505 541 134 585 293 383 232 330 424 438 348 447 249 438 434 628 281 384 172 249 319 603 272 487 20 557 374 490 149 430 499 548 239 318 633 634 299 307 202 276 209 390 159 401 344 539 31 223 191 341 385 463 613 617 339 501 448 456 13 316 149 201 261 354 437 556 172 464 487 518 303 526 96 612 126 367 154 505 312 554 429 442 130 324 108 396 84 448 104 230 102 393 145 533 509 531 59 256 371 602 5 501 9 125 121 170 78 549 548 575 71 169 346 609 152 351 507 544 503 567 315 326 452 598 15 452 518 571 190 454 38…
Output: 7

Example 3:

Input: 248 1257 1 248 66 115 80 199 117 153 26 220 52 168 26 93 64 146 16 52 57 96 23 190 37 242 29 175 113 140 168 234 51 76 94 110 27 101 72 231 35 108 138 232 145 165 105 240 34 246 49 240 144 228 20 134 76 118 6 113 52 114 178 194 81 130 9 42 14 32 202 227 105 165 83 246 111 127 168 229 50 113 95 167 117 186 99 197 95 217 7 156 195 232 115 127 91 233 97 142 115 191 22 175 128 188 119 236 75 236 65 103 112 147 26 222 194 199 12 189 203 226 101 138 84 216 135 221 80 95 125 237 41 69 142 179 75 91 129 240 190 205 68 140 106 219 214 220 19 87 102 196 47 120 90 195 4 104 101 136 9 200 131 201 54 116 62 95 20 158 20 186 60 144 97 124 111 189 141 223 190 192 1 243 32 146 36 165 35 193 52 215 180 233 3 150 61 211 41 164 118 145 37 88 160 231 122 142 125 223 148 215 44 175 103 233 124 234 14 214 68 12…
Output: 3

Constraints:

1 <= n <= 1199; 0 <= m <= 2398.

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