CT29648

Dorian's Wistful canals

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Dorian inherited the loom house at the honey farms of Buzzwell along with its curious bookkeeping system for canals. Time to make sense of it. 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 <= 718; 0 <= m <= 1436.

Example 1:

Input: 393 1380 1 393 18 41 20 87 54 257 149 181 45 238 215 363 327 352 159 210 27 196 34 133 173 271 94 142 75 172 248 365 152 241 60 329 249 251 147 250 43 205 99 348 110 356 115 335 119 271 34 78 298 351 4 306 59 374 249 290 226 382 222 325 37 373 117 349 288 351 234 313 42 328 52 262 265 364 39 254 2 221 32 178 80 321 52 110 119 188 44 353 87 210 156 317 186 322 69 367 331 364 172 306 386 393 121 278 27 225 206 245 40 240 50 63 129 220 10 273 141 317 131 213 103 319 97 358 129 157 281 303 44 308 318 331 44 45 58 339 79 358 93 219 168 354 47 67 118 351 102 302 114 209 34 157 331 350 144 218 122 206 222 369 33 72 173 240 26 147 159 193 276 377 173 280 119 169 53 61 4 380 75 319 322 348 216 280 42 160 223 382 257 344 215 377 6 25 190 237 116 293 172 262 134 291 292 297 96 243 195 358 316 333 61 …
Output: 3

Example 2:

Input: 12 66 1 12 2 3 5 7 8 12 7 8 2 9 7 12 3 8 9 12 1 12 11 12 1 5 2 10 4 11 4 9 4 5 5 10 3 10 2 5 1 4 6 11 3 11 5 6 1 9 2 7 2 8 3 4 6 7 7 11 6 12 4 7 10 12 7 9 4 8 5 9 9 10 1 7 8 11 8 9 4 6 3 9 9 11 3 12 5 8 4 10 7 10 1 3 3 5 1 6 4 12 3 6 1 11 6 9 5 12 8 10 1 8 6 10 2 4 10 11 6 8 2 6 5 11 1 10 2 11 1 2 2 12 3 7
Output: 1

Example 3:

Input: 11 55 1 11 2 11 2 7 2 8 3 11 1 8 1 6 2 6 4 9 5 6 1 11 2 3 2 4 1 10 3 10 4 10 2 9 3 4 5 11 4 8 7 9 9 10 1 9 6 10 6 8 8 10 4 7 1 4 5 7 6 7 6 9 4 6 1 3 7 10 1 7 7 8 6 11 2 5 1 2 5 8 9 11 3 9 3 8 4 5 8 9 3 5 5 9 10 11 5 10 2 10 8 11 1 5 3 7 7 11 4 11 3 6
Output: 1

Constraints:

1 <= n <= 718; 0 <= m <= 1436.

Loading...
Test Cases:No test cases
No test cases available.
Dorian's Wistful canals - MEDIUM Coding Problem | CodeTikki