CT30662

Rune Counts the roads

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Deep in the mining town of Ironvein, Rune studies rows of roads entries. One clean number will settle the guild's oldest argument. 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: 584 915 1 584 418 500 464 475 143 260 27 297 28 301 338 549 159 321 466 526 79 510 49 543 81 100 348 511 461 567 141 221 373 486 432 576 116 286 281 538 68 436 12 19 298 368 300 529 163 220 106 270 143 533 163 525 128 533 82 110 272 477 227 274 238 327 101 154 189 252 185 375 491 560 45 132 552 571 392 544 120 197 131 571 184 294 96 194 32 198 373 388 25 522 330 529 400 472 140 206 88 351 123 437 288 575 438 522 76 78 152 424 169 239 193 402 320 343 56 117 251 553 556 571 243 494 67 272 227 381 418 459 19 391 280 549 58 254 39 328 186 510 195 527 193 501 187 204 449 570 9 457 229 280 200 529 277 325 50 475 83 478 321 411 41 264 362 486 42 533 200 206 186 351 91 96 242 320 404 470 326 414 176 426 204 497 21 474 100 529 477 508 136 221 5 122 261 311 156 564 6 164 73 334 221 442 185 419 510 5…
Output: 6

Example 2:

Input: 553 552 1 553 238 359 218 296 213 251 192 218 128 456 420 495 241 365 50 97 93 546 140 259 74 172 35 406 79 160 428 510 41 178 53 126 250 384 91 545 283 461 127 393 312 358 80 413 55 159 214 338 514 551 92 109 326 537 196 437 132 468 52 489 211 303 63 274 240 403 146 202 117 275 93 119 194 553 72 299 252 377 7 145 223 484 452 550 346 471 356 517 60 204 1 305 40 443 51 430 34 174 172 194 181 437 73 395 44 390 301 485 168 378 88 472 430 449 30 544 3 39 331 465 415 420 165 353 25 355 104 357 32 387 15 340 9 252 141 184 158 237 16 143 25 227 492 513 189 299 295 337 94 189 43 311 410 449 119 398 189 296 101 165 203 256 63 499 213 340 152 214 26 460 165 273 228 307 268 424 22 93 136 282 177 211 193 227 123 172 362 458 432 513 249 283 123 487 266 382 176 343 38 492 71 330 135 173 276 440 75 212 1…
Output: 4

Example 3:

Input: 132 747 1 132 16 132 103 124 14 106 61 124 37 105 26 79 22 119 56 97 126 127 31 81 10 95 15 103 42 102 4 13 83 89 18 86 13 118 56 126 67 108 10 75 5 129 32 59 46 88 82 120 14 83 26 31 103 118 25 123 22 59 16 103 44 91 54 127 73 114 65 70 20 83 84 100 18 67 87 121 10 92 64 74 20 101 19 82 71 90 34 110 65 95 47 106 22 105 36 69 42 131 28 63 44 64 98 106 110 117 79 126 90 115 99 120 43 114 32 66 64 125 31 122 22 46 62 126 56 111 109 126 74 103 16 69 90 100 39 63 60 132 35 122 32 71 5 54 32 69 67 75 7 66 7 95 28 99 5 89 50 96 6 98 27 50 76 124 27 44 112 115 38 123 46 130 28 48 33 122 63 82 4 29 8 97 46 68 17 75 13 80 9 130 24 94 13 33 75 99 45 93 50 101 100 105 50 51 27 101 67 111 97 130 58 78 46 120 83 107 32 88 49 121 104 115 69 114 32 103 16 121 44 55 1 8 39 77 31 79 50 116 25 99 23 132 2 1…
Output: 2

Constraints:

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

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