CT44395

The Fewest Hops Beneath Tidewater

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the coastal hub of Tidewater, Aria the log keeper keeps careful count of the tunnels. rank apprentices for the new term, every figure matters. 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 <= 1016; 0 <= m <= 2032.

Example 1:

Input: 461 460 1 461 106 385 245 289 354 380 41 139 241 268 84 124 34 289 74 150 215 359 107 258 44 89 183 384 30 253 120 211 279 418 217 323 302 456 73 440 346 438 54 294 117 233 47 434 199 238 58 240 148 288 141 239 35 38 226 385 176 288 30 49 191 453 290 346 66 117 184 293 156 416 125 459 75 360 336 368 165 461 101 442 158 226 49 373 69 399 279 308 3 330 373 400 271 415 56 208 28 273 243 456 287 411 186 207 180 461 161 333 106 287 88 111 25 236 158 421 59 172 37 365 125 153 21 354 155 182 192 308 208 282 231 326 67 91 304 418 128 274 101 353 159 168 42 450 158 339 97 189 343 377 147 275 144 330 298 449 295 367 379 385 136 349 92 181 83 136 9 194 10 415 190 198 155 446 94 203 304 424 338 357 38 192 48 60 1 22 66 301 169 184 393 420 284 368 92 153 277 371 158 371 116 287 114 186 305 437 111 203 …
Output: 6

Example 2:

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

Example 3:

Input: 299 298 1 299 14 193 64 97 65 129 87 247 149 193 24 60 119 272 287 299 187 299 6 202 95 213 184 212 103 272 171 231 92 227 48 273 3 149 37 123 30 129 33 124 185 252 129 212 59 266 221 237 74 209 1 199 153 169 58 150 29 37 94 217 20 101 15 210 37 162 165 218 66 170 42 107 212 293 63 84 64 258 232 267 38 292 79 259 47 221 57 84 154 190 74 184 136 227 7 84 35 93 98 151 129 138 10 268 200 244 212 264 161 263 18 252 34 68 82 264 45 276 69 281 5 250 83 111 26 56 69 238 41 152 14 246 16 80 164 179 128 198 14 179 29 204 18 130 127 157 96 211 80 266 72 103 152 293 67 134 76 284 35 64 229 241 186 192 61 81 45 292 12 121 213 247 110 251 104 221 134 195 18 213 100 152 82 181 67 228 180 225 112 212 28 67 117 263 70 141 119 252 207 234 27 93 74 203 47 84 144 207 52 250 68 240 55 217 13 95 159 171 151 26…
Output: 8

Constraints:

1 <= n <= 1016; 0 <= m <= 2032.

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