CT49508

The Smoky roads of Cartwright

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The inventory keeper Cartwright has been asked to rank apprentices for the new term. On the desk lies a long table of roads 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 <= 1047; 0 <= m <= 2094.

Example 1:

Input: 92 1332 1 92 32 84 39 70 51 80 2 83 23 44 27 59 58 80 27 63 50 61 8 76 62 78 80 92 38 85 58 72 71 89 71 80 52 79 3 89 14 19 33 39 16 27 30 46 15 21 22 61 27 86 16 91 4 22 4 62 43 90 13 69 54 88 72 78 4 71 5 30 9 57 40 42 12 40 25 47 20 90 58 83 59 60 29 51 5 21 14 92 39 73 10 77 9 17 32 68 36 92 65 68 20 44 73 91 49 88 69 74 34 37 33 43 8 37 46 75 56 74 13 67 16 38 46 72 29 64 23 32 22 79 71 74 32 48 26 34 47 55 11 37 41 56 27 85 20 81 11 14 24 50 47 91 36 55 59 87 12 35 25 78 10 56 18 74 36 52 25 77 36 51 38 81 27 74 55 83 6 14 9 26 8 34 73 76 17 84 21 57 24 86 12 51 46 89 15 17 26 27 41 78 78 90 11 32 18 21 46 77 45 92 45 57 14 43 15 63 27 68 61 69 28 35 31 78 3 34 24 70 10 79 16 73 70 77 12 32 78 91 29 39 67 70 24 56 26 43 66 80 24 52 75 82 74 83 4 37 16 53 70 78 19 78 82 92 62 88 41 70…
Output: 1

Example 2:

Input: 550 549 1 550 27 342 69 492 141 205 215 277 431 469 22 434 113 336 112 244 223 331 503 514 205 404 490 495 52 379 349 422 208 478 401 530 70 336 122 411 400 499 306 363 162 263 438 549 284 432 90 390 48 103 400 505 75 412 30 459 488 520 481 493 68 334 169 482 459 493 67 200 439 544 72 550 194 459 170 190 465 531 42 530 110 193 60 472 85 238 11 69 19 386 56 478 57 123 94 440 48 288 49 536 161 499 159 297 54 394 134 435 230 283 452 498 178 445 377 494 217 498 102 334 279 535 209 383 160 289 117 351 300 310 318 371 144 374 65 274 18 514 162 454 405 469 172 256 32 392 53 199 274 339 180 402 178 259 36 380 127 267 390 406 21 303 56 185 120 233 61 284 139 491 1 283 4 18 410 425 58 372 507 519 134 253 177 240 205 414 82 456 316 470 282 394 450 526 314 459 460 542 62 487 102 167 68 401 51 388 67 4…
Output: 13

Example 3:

Input: 507 506 1 507 413 466 104 287 137 143 347 467 56 158 131 155 158 257 130 275 139 322 202 427 177 201 376 474 37 343 391 484 223 354 28 139 44 359 221 328 55 185 89 377 43 74 181 189 373 487 309 488 82 361 1 462 192 504 225 294 69 82 1 214 243 456 229 455 379 442 10 498 116 178 224 413 326 388 185 364 8 251 145 353 235 423 221 276 51 349 45 461 17 76 228 307 296 507 91 441 86 386 75 242 59 229 22 396 253 298 199 418 30 72 79 448 224 312 126 475 129 435 239 279 213 329 130 327 15 132 8 409 106 185 152 404 9 61 211 381 1 267 244 437 154 232 77 459 71 180 22 211 134 472 388 412 316 403 80 435 175 342 336 359 32 448 216 283 352 494 130 433 66 124 22 115 67 363 393 487 242 329 170 403 147 315 305 331 311 486 238 376 149 210 40 422 66 160 120 283 13 314 7 399 366 374 68 388 95 212 15 208 75 395 2…
Output: 8

Constraints:

1 <= n <= 1047; 0 <= m <= 2094.

Loading...
Test Cases:No test cases
No test cases available.
The Smoky roads of Cartwright - MEDIUM Coding Problem | CodeTikki