CT35344

The Fewest Hops Beneath Glimmerfell

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the quartz ridge of Glimmerfell opens only for a perfect tally of routes. Kabir means to find out. 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 <= 1840; 0 <= m <= 3680.

Example 1:

Input: 945 1736 1 945 379 782 68 196 633 930 73 840 358 925 121 173 64 818 592 839 144 149 279 310 365 835 203 216 636 815 439 563 524 783 289 865 534 913 506 667 14 282 156 214 260 595 81 726 42 261 4 608 91 413 149 558 447 940 367 373 166 676 57 291 137 795 340 806 251 490 264 296 168 467 442 515 343 837 645 919 223 686 326 667 167 229 157 679 69 892 48 418 422 441 543 695 115 311 670 912 471 651 115 524 119 699 402 942 37 439 130 296 376 926 866 875 153 260 617 638 274 317 193 275 693 936 126 430 284 541 99 610 484 743 172 753 222 373 467 863 373 661 38 761 509 596 125 943 479 566 459 520 282 652 434 630 566 943 824 914 472 575 457 716 159 198 258 455 670 930 900 916 149 667 110 536 111 802 341 477 69 718 615 635 91 432 271 372 506 538 456 467 12 232 158 336 331 428 648 712 791 894 294 645 121…
Output: 3

Example 2:

Input: 228 2187 1 228 16 171 136 178 76 113 96 177 103 143 194 210 15 135 93 145 127 150 28 151 23 74 33 193 96 149 165 210 91 101 32 143 70 86 191 220 30 65 23 99 22 73 88 184 125 208 16 174 55 168 18 173 122 209 151 185 145 178 117 173 45 74 85 94 28 171 45 190 29 194 106 120 37 146 2 212 67 220 27 72 69 97 19 56 2 217 16 73 133 136 69 170 158 220 135 179 87 146 99 154 109 218 163 165 96 116 13 171 127 189 110 135 11 196 43 178 75 215 24 43 88 102 50 90 12 56 15 223 63 142 27 223 56 87 15 181 163 189 93 132 84 119 108 175 169 193 25 108 27 167 67 146 16 132 91 157 106 206 61 92 203 215 34 214 137 138 15 157 58 149 122 206 79 126 181 215 113 135 13 14 120 209 12 59 40 168 186 222 157 220 162 218 16 160 57 141 91 171 26 39 82 120 22 38 23 226 8 188 34 39 162 184 120 151 127 224 47 193 106 167 55 …
Output: 1

Example 3:

Input: 78 239 1 78 30 35 28 65 12 23 12 52 45 61 5 38 36 71 19 73 38 58 15 37 10 26 24 52 53 57 26 40 45 54 21 78 1 55 42 43 5 61 37 60 5 10 23 71 58 74 59 67 63 69 27 70 31 71 27 46 14 31 46 51 34 45 18 37 40 43 7 15 10 55 1 78 67 70 29 62 9 39 35 64 49 77 6 50 58 61 15 43 29 38 21 59 23 51 33 41 51 52 44 66 37 58 25 48 39 62 17 20 36 56 18 36 57 72 39 45 42 54 15 26 1 44 13 28 43 62 59 68 50 69 47 50 54 63 41 49 31 69 26 69 4 40 4 47 35 75 1 41 1 51 11 43 20 54 46 65 23 33 40 56 46 48 3 62 13 53 58 65 1 18 71 72 38 44 7 51 16 45 50 51 38 39 60 63 3 20 19 50 47 60 21 40 8 10 69 74 13 45 2 66 16 55 3 31 20 28 53 66 16 33 18 72 16 68 35 77 3 60 5 16 7 68 57 74 2 75 36 47 71 77 42 47 62 76 16 67 17 32 11 47 12 55 47 73 19 47 1 74 67 77 14 59 3 8 24 37 46 52 14 51 14 44 13 14 14 49 13 39 9 66 1 33 1…
Output: 1

Constraints:

1 <= n <= 1840; 0 <= m <= 3680.

Loading...
Test Cases:No test cases
No test cases available.
The Fewest Hops Beneath Glimmerfell - MEDIUM Coding Problem | CodeTikki