CT53273

Last corridors of Notary

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Notary inherited the cooperage at the temple city of Sunspire along with its curious bookkeeping system for corridors. 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 <= 1979; 0 <= m <= 3958.

Example 1:

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

Example 2:

Input: 598 1207 1 598 3 118 473 594 525 574 29 342 283 327 314 442 209 474 227 298 267 383 134 575 180 541 421 443 363 470 180 370 114 347 182 590 220 376 377 593 95 265 137 274 129 429 259 582 100 318 97 476 267 402 149 460 133 376 290 448 78 514 216 446 34 397 391 594 130 149 156 517 478 564 34 176 284 333 284 350 91 147 144 151 3 79 279 318 21 343 384 419 211 325 495 527 343 419 306 435 163 578 40 404 241 433 163 567 261 533 21 385 550 591 356 548 168 260 270 408 446 491 119 471 374 436 67 74 203 258 12 298 21 263 97 325 96 458 190 416 170 332 28 527 568 597 7 452 376 398 312 476 278 539 258 567 304 537 274 341 44 310 15 293 368 512 186 311 338 361 465 529 158 235 79 354 54 232 66 508 84 181 152 441 311 501 368 584 31 40 37 80 128 547 36 317 329 474 446 568 342 418 47 447 97 565 3 584 8 20 61 …
Output: 4

Example 3:

Input: 365 2602 1 365 178 187 26 363 26 270 220 328 45 350 195 242 215 346 5 221 136 156 96 333 112 262 66 227 47 164 298 327 27 117 244 315 96 243 4 117 3 44 177 357 63 102 174 273 78 159 19 191 7 147 16 93 36 345 86 129 113 202 7 76 209 320 97 159 55 99 69 325 234 285 320 358 245 335 76 365 61 209 309 340 59 345 48 78 54 109 53 153 115 302 3 312 293 329 105 223 125 145 29 226 183 258 58 205 27 271 226 281 196 319 8 25 96 178 108 180 64 226 280 347 6 286 85 342 10 18 207 269 124 310 282 290 34 133 69 75 202 332 78 99 135 260 112 134 39 150 9 344 35 175 285 346 191 270 329 353 85 185 58 281 51 243 227 280 19 60 96 161 326 352 158 197 90 279 120 330 57 363 33 334 68 175 67 74 178 309 111 115 12 26 109 296 223 242 278 284 147 296 200 319 204 313 42 337 45 103 10 259 58 181 38 303 76 233 7 176 276 3…
Output: 3

Constraints:

1 <= n <= 1979; 0 <= m <= 3958.

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