CT39083

Last bridges of Quill

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Quill the dispatch writer watches over the coral atoll of Pearldeep's stores of bridges. A careful computation stands between order and chaos. 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 <= 1163; 0 <= m <= 2326.

Example 1:

Input: 398 2293 1 398 354 398 226 391 56 174 284 348 147 392 229 318 71 277 19 67 210 344 43 104 70 116 25 77 295 319 136 233 302 311 113 172 182 317 30 286 2 111 195 235 204 354 322 390 149 324 144 232 317 354 76 162 50 374 120 239 81 133 100 240 164 308 81 398 120 339 199 386 137 208 58 131 63 268 7 112 19 343 98 162 47 322 101 373 102 185 124 339 15 367 76 223 225 360 53 133 10 70 210 264 180 329 79 134 243 378 112 212 277 389 115 182 382 398 66 311 371 376 50 168 103 373 90 346 61 266 236 284 137 265 182 374 133 328 11 157 337 342 314 325 75 361 33 328 86 276 130 294 12 342 123 349 231 335 198 226 54 344 236 353 100 289 299 379 203 349 71 380 110 381 200 247 281 372 183 318 10 179 156 321 99 397 233 258 220 318 253 282 99 162 280 284 240 272 38 296 318 353 224 377 132 225 194 277 196 233 35 2…
Output: 3

Example 2:

Input: 936 1807 1 936 87 335 368 689 518 917 115 124 467 480 258 478 30 527 12 428 234 702 764 773 81 252 330 406 56 559 161 843 277 882 113 623 95 186 534 792 62 161 18 584 175 818 57 719 771 867 486 574 70 711 871 924 315 771 156 628 347 613 588 755 262 735 533 727 234 841 289 825 207 545 436 735 815 929 128 699 409 840 157 827 623 927 328 534 25 183 336 651 753 860 618 652 446 474 22 447 179 548 509 696 133 561 350 555 23 79 396 544 39 438 809 834 533 611 276 671 476 782 228 769 111 271 76 157 194 285 175 503 255 577 803 835 354 718 845 921 22 693 88 576 424 797 367 373 246 771 437 801 278 476 12 412 110 786 122 391 247 867 444 863 304 358 277 711 618 867 460 791 19 104 518 599 820 859 459 625 205 361 282 919 394 667 649 730 530 747 120 543 165 365 9 256 211 489 429 614 193 395 234 731 689 709…
Output: 5

Example 3:

Input: 161 160 1 161 45 83 67 158 33 79 7 13 91 118 87 115 110 152 70 86 86 135 118 143 122 141 100 158 18 127 86 136 88 98 5 117 12 113 59 115 5 7 134 143 82 94 3 117 86 138 10 49 77 109 34 120 5 19 117 142 78 154 52 139 46 147 152 160 45 62 54 90 22 137 7 53 76 123 44 123 3 107 75 137 89 148 137 150 92 93 8 114 92 144 6 108 58 105 5 16 109 113 104 121 5 118 118 119 37 70 23 145 4 60 6 128 113 130 29 123 58 85 79 96 78 152 14 119 57 63 65 94 96 103 12 132 111 144 10 45 5 31 42 112 8 153 47 63 45 139 48 61 13 65 19 63 89 92 98 156 61 125 45 137 101 158 122 145 38 131 27 136 92 109 39 113 102 127 128 157 7 21 30 149 78 92 42 114 25 123 69 82 121 151 26 81 68 91 93 105 12 97 95 123 36 124 40 41 86 137 6 53 40 109 106 133 15 62 66 74 32 92 92 104 122 159 126 138 60 88 104 145 11 155 74 86 38 155 146…
Output: 10

Constraints:

1 <= n <= 1163; 0 <= m <= 2326.

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