CT32714

The Fewest Hops Beneath Thimblewick

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Deep in the wren hedges of Thimblewick, Zoya studies rows of roads entries. One clean number will settle the guild's oldest argument. 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 <= 1508; 0 <= m <= 3016.

Example 1:

Input: 1294 1313 1 1294 443 638 189 226 131 801 163 931 929 1137 713 1211 194 974 222 653 78 866 898 1015 51 1116 327 825 354 526 714 987 643 1094 8 1086 71 144 21 1210 392 1087 142 299 529 953 600 977 22 817 212 323 769 1231 298 374 655 945 343 816 92 1266 171 384 21 427 104 1077 874 997 199 781 728 1291 836 872 108 854 666 908 592 965 820 1075 766 975 94 608 1011 1100 556 894 103 1067 313 718 643 1038 69 527 201 236 292 789 597 1036 93 729 107 559 1047 1088 258 902 500 1014 396 1235 462 827 286 890 374 902 629 763 172 539 869 959 589 650 132 1262 414 1076 173 686 597 942 18 128 908 1158 554 736 286 1010 496 657 493 1265 440 742 110 674 368 1292 36 889 656 1187 10 1227 228 827 847 932 619 947 927 1184 24 667 276 1034 1106 1254 875 876 909 1025 395 1001 833 1163 272 912 274 1160 326 413 566 729 3…
Output: 14

Example 2:

Input: 254 2600 1 254 3 172 59 119 28 117 95 157 29 32 164 250 4 144 179 187 21 132 31 168 160 186 49 233 28 102 65 230 17 160 124 182 77 173 45 158 15 134 10 84 56 250 3 9 206 240 70 196 109 148 23 102 76 164 199 229 59 60 95 206 148 217 187 237 45 135 4 9 166 214 134 244 12 254 96 124 4 232 214 239 42 93 5 72 58 213 49 159 178 219 105 175 108 220 29 233 120 204 99 138 10 207 48 74 1 160 176 180 59 239 29 242 15 76 5 150 32 34 74 78 88 168 57 189 61 74 12 126 169 210 98 198 84 246 141 248 183 197 216 232 6 157 195 208 35 48 42 179 46 120 81 202 37 186 35 85 108 117 36 48 163 224 125 140 142 221 116 154 103 118 69 193 63 127 40 179 110 235 200 233 174 224 147 182 20 130 12 69 12 46 124 200 90 225 2 110 98 228 52 194 59 83 11 247 216 251 174 243 193 231 121 142 32 41 30 170 50 180 115 198 96 144 2…
Output: 2

Example 3:

Input: 209 2321 1 209 99 125 91 185 98 178 41 185 60 183 28 35 59 140 93 158 97 206 63 72 26 136 94 176 37 172 12 35 17 70 74 148 47 128 117 145 38 57 28 87 111 175 9 38 3 39 115 188 121 176 39 195 114 129 123 197 142 181 29 35 29 168 105 186 50 190 115 167 101 203 135 144 3 101 172 178 35 139 122 142 43 208 77 192 163 185 35 90 169 178 11 87 72 127 100 131 33 188 110 134 2 197 57 74 75 197 21 107 46 158 41 167 14 177 75 92 10 140 20 50 72 77 64 167 38 107 19 41 19 125 70 206 14 178 6 117 34 173 9 189 109 158 141 184 96 98 34 90 144 156 73 209 12 122 126 151 4 191 112 123 88 115 2 122 31 181 14 37 65 156 45 80 61 130 93 156 61 88 152 167 6 113 96 131 3 15 31 58 106 143 10 102 20 188 8 108 130 207 43 189 121 170 46 197 30 49 131 132 82 87 57 178 131 175 60 68 36 136 143 201 47 142 61 108 172 190 2…
Output: 2

Constraints:

1 <= n <= 1508; 0 <= m <= 3016.

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