CT45051

The Fewest Hops of Saprun

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The clerk Clerk has been asked to verify the ledger before the auditors arrive. On the desk lies a long table of canals readings. 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 <= 1171; 0 <= m <= 2342.

Example 1:

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

Example 2:

Input: 407 1009 1 407 190 315 118 190 96 357 95 390 105 144 31 263 15 97 61 150 163 367 153 178 49 323 179 307 84 310 80 191 256 334 91 178 107 319 15 175 57 369 52 333 203 385 181 363 267 383 351 373 113 272 74 339 318 356 106 396 143 406 45 76 79 331 48 78 70 311 167 372 188 360 63 145 115 401 59 289 209 382 332 384 185 195 282 340 273 359 112 339 192 347 203 218 185 268 97 165 268 350 103 332 82 251 84 265 98 167 187 351 314 378 109 339 95 122 27 352 44 119 11 293 57 111 143 151 47 130 42 55 62 164 118 168 46 162 54 286 31 193 13 182 16 108 70 258 178 224 234 398 135 266 313 366 205 218 82 244 142 240 245 246 142 382 89 196 206 217 59 106 238 265 167 344 52 399 95 236 161 334 116 182 164 217 77 167 156 324 44 363 241 325 19 102 365 375 208 372 118 180 102 223 241 322 17 71 353 379 148 303 50 3…
Output: 3

Example 3:

Input: 614 1106 1 614 24 377 13 536 241 327 99 489 62 593 198 439 290 578 526 541 84 297 111 144 107 148 115 492 149 315 102 351 356 469 268 480 29 218 57 264 451 528 317 448 391 514 178 527 310 586 19 217 405 463 333 381 333 406 360 404 164 456 4 383 11 125 131 448 496 555 72 190 271 509 29 189 472 560 179 357 106 162 129 334 178 436 97 139 18 485 88 192 207 422 144 180 171 534 529 576 374 504 63 76 239 587 162 526 535 563 83 424 56 595 252 445 354 611 267 368 230 344 431 478 426 603 252 567 212 451 102 135 102 418 154 332 77 486 100 608 103 604 36 526 29 551 116 295 12 249 276 592 484 524 251 575 452 547 100 341 516 577 183 371 29 364 381 512 242 461 50 367 178 579 8 217 262 280 406 431 56 520 69 237 148 298 304 490 237 248 132 402 232 278 286 291 264 435 25 573 65 342 252 330 50 483 32 306 19 …
Output: 5

Constraints:

1 <= n <= 1171; 0 <= m <= 2342.

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