CT30386

Dante and the Brass routes

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

It is audit day at the quays of Driftwood. Dante spreads the routes records across the table and picks up a sharp pencil. 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 <= 1317; 0 <= m <= 2634.

Example 1:

Input: 547 2069 1 547 327 426 49 89 229 411 193 233 146 485 25 462 275 369 135 371 208 545 167 245 228 386 302 522 134 268 42 130 220 378 16 231 83 343 224 385 234 449 255 461 133 528 55 459 243 377 327 338 190 412 140 407 242 421 60 383 22 364 36 153 371 512 396 415 185 296 20 121 42 188 41 388 364 406 345 378 43 448 422 509 399 503 38 191 72 249 393 408 2 269 124 189 47 499 101 520 311 509 197 383 333 398 34 531 300 316 116 143 22 168 204 316 192 275 62 382 59 269 78 373 109 517 90 300 10 241 136 371 35 48 488 502 401 437 396 492 171 234 514 517 306 353 30 46 104 347 14 55 91 100 79 536 84 87 207 326 227 241 80 189 154 506 35 55 129 196 111 501 30 453 181 277 243 474 69 237 35 321 174 445 321 419 141 215 124 382 162 172 306 351 59 435 78 493 332 510 169 543 68 349 93 168 414 538 25 140 216 296 …
Output: 4

Example 2:

Input: 1168 1167 1 1168 3 1011 83 291 262 893 163 1167 433 825 387 1078 327 1093 862 877 733 1103 366 1060 21 1070 881 931 121 1076 60 308 801 1099 940 1122 691 852 258 345 373 707 999 1011 502 1095 179 775 469 658 499 1125 928 1003 650 967 635 841 76 452 327 1095 555 988 40 89 851 1066 514 1133 626 998 9 840 56 670 652 1132 614 1076 184 750 426 511 261 490 451 1127 238 630 43 315 213 774 959 999 340 685 174 670 67 924 541 621 664 719 333 898 391 591 752 888 589 691 504 1086 299 783 219 431 453 1042 428 610 861 868 459 572 1160 1168 595 1143 453 681 613 815 398 585 727 947 610 945 156 240 461 1059 270 930 672 928 123 543 261 802 183 463 917 988 314 739 567 604 83 1035 641 1114 762 1084 503 1070 464 837 920 1156 781 980 92 772 139 322 162 495 121 922 13 127 887 1096 970 1166 339 700 36 379 120 567…
Output: 9

Example 3:

Input: 407 2492 1 407 151 257 166 331 36 199 139 256 209 256 2 226 233 371 215 357 65 114 63 373 120 282 110 207 86 150 70 291 252 354 63 358 87 97 92 406 168 288 190 361 196 245 24 373 148 179 43 150 189 376 295 406 200 338 30 301 27 179 185 341 1 129 281 301 13 398 267 381 64 84 258 278 266 347 130 139 339 395 175 184 319 398 188 363 92 237 269 310 131 316 28 203 288 316 21 339 170 218 230 397 4 60 176 312 84 367 153 254 63 123 173 322 54 114 89 369 136 380 15 202 135 317 67 207 145 333 238 242 99 319 50 274 215 245 128 220 73 378 26 33 311 394 255 309 24 207 202 257 173 393 224 314 136 245 84 287 269 370 173 326 170 268 192 217 84 133 28 189 18 348 156 352 253 330 8 62 47 220 66 238 24 156 124 325 4 288 24 150 61 156 172 189 165 350 214 262 73 306 77 232 250 256 157 159 81 136 88 260 106 337 9…
Output: 3

Constraints:

1 <= n <= 1317; 0 <= m <= 2634.

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