CT31948

Asha's Misty bridges

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

In the port of Emberfall, Asha the archivist keeps careful count of the bridges. rebuild the damaged itinerary, 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 <= 1010; 0 <= m <= 2020.

Example 1:

Input: 43 903 1 43 33 38 4 7 12 39 22 34 7 31 1 22 23 33 29 40 11 34 29 33 22 29 23 26 31 34 32 36 18 30 2 41 7 13 21 30 16 36 24 33 25 41 14 20 18 31 14 17 23 29 2 6 9 43 22 42 12 22 34 39 14 31 16 22 18 35 22 37 11 29 14 34 8 37 17 38 18 20 18 39 26 28 20 23 27 39 10 12 24 40 11 15 8 29 6 7 21 24 22 36 6 14 14 35 30 37 9 13 3 6 23 43 30 36 18 38 6 42 3 30 31 43 3 31 28 29 1 5 4 18 3 17 11 25 13 41 1 38 5 16 12 13 37 40 11 41 25 38 11 36 12 19 1 24 5 13 9 34 38 43 13 33 6 33 20 41 19 32 19 36 18 24 2 26 14 16 24 35 16 27 13 21 12 25 1 20 15 41 9 20 35 43 26 38 28 41 2 15 13 23 7 21 20 32 10 36 21 43 9 27 17 34 12 36 25 26 26 37 8 16 23 28 14 26 23 37 17 40 13 22 9 12 12 16 3 26 31 39 16 35 25 40 17 39 20 43 7 11 10 38 37 39 21 42 5 33 5 14 5 15 6 29 5 27 8 11 10 22 1 6 17 36 10 29 4 8 16 32 9 15…
Output: 1

Example 2:

Input: 412 1813 1 412 5 15 350 408 21 309 204 255 244 275 210 269 81 114 127 192 40 143 36 78 40 71 53 403 105 391 32 159 167 378 228 257 275 297 41 62 100 228 56 341 47 99 5 91 196 266 96 137 153 327 202 270 43 186 181 402 70 345 155 393 234 354 330 352 192 276 199 401 178 204 258 385 129 175 158 310 154 357 86 330 210 359 71 184 141 161 147 375 223 268 103 127 214 346 69 333 67 72 37 403 172 391 19 67 48 189 361 378 208 380 147 201 26 387 1 263 8 49 312 376 189 343 204 313 247 304 1 65 180 192 346 392 256 289 153 329 49 83 39 232 245 402 253 350 254 332 370 380 178 368 2 229 25 261 135 276 39 126 206 380 94 203 63 259 1 352 96 186 121 408 76 84 105 266 149 235 39 299 129 344 250 265 25 306 188 322 170 382 29 265 55 284 129 330 157 178 106 151 193 374 166 400 25 83 179 384 14 332 287 402 289 337…
Output: 3

Example 3:

Input: 489 488 1 489 301 390 107 246 140 206 199 223 223 370 397 484 74 381 104 261 5 227 390 422 29 358 410 441 322 362 180 310 78 103 4 302 213 352 70 96 213 230 43 464 166 402 42 203 82 127 304 415 115 376 226 408 160 398 359 433 179 196 8 29 94 341 221 321 229 398 227 394 139 340 303 424 10 224 118 360 83 346 128 143 193 219 224 244 9 22 421 482 222 390 305 403 28 299 199 286 35 399 156 449 298 309 62 335 18 264 19 285 203 266 15 29 251 313 465 473 70 415 261 329 95 308 205 267 362 372 385 447 303 481 300 450 60 171 411 414 73 106 190 338 202 248 279 370 142 257 250 413 15 423 203 356 21 191 238 446 34 229 123 278 113 412 244 402 8 188 210 259 84 375 157 356 32 182 91 97 34 63 209 331 357 417 182 264 177 304 12 200 9 18 150 448 121 312 25 151 327 437 191 488 157 351 4 484 69 209 136 346 177 2…
Output: 9

Constraints:

1 <= n <= 1010; 0 <= m <= 2020.

Loading...
Test Cases:No test cases
No test cases available.
Asha's Misty bridges - MEDIUM Coding Problem | CodeTikki