CT34744

Orin's corridors Reckoning

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

The valuer Orin has been asked to verify the safety inspections. On the desk lies a long table of corridors 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 <= 1382; 0 <= m <= 2764.

Example 1:

Input: 1217 1435 1 1217 179 476 194 346 147 466 104 154 329 453 26 96 162 373 49 305 899 1050 536 1208 404 434 295 406 86 494 708 896 1015 1058 520 982 12 887 1006 1017 901 1008 168 216 140 1020 574 609 443 1005 287 708 156 1080 73 899 119 863 604 1099 47 248 107 765 516 831 890 1160 498 913 109 615 502 1082 929 1051 41 1092 507 716 555 1016 442 761 117 1047 197 345 340 814 276 626 30 1017 369 978 442 653 48 209 143 486 122 910 951 1165 422 578 604 755 29 403 260 639 41 264 211 368 744 1203 132 731 70 574 221 785 824 1169 746 825 486 1086 874 932 895 906 507 1137 169 639 1106 1126 839 1199 39 851 158 859 82 843 19 781 762 864 731 915 247 1070 828 1058 187 1021 116 1052 986 999 360 803 877 1167 344 721 389 430 27 793 940 1044 627 809 340 1105 417 1039 693 1174 628 980 170 1089 106 955 379 869 327 …
Output: 9

Example 2:

Input: 1319 1318 1 1319 760 1305 50 704 761 1238 721 816 859 1198 771 1109 205 498 714 1209 334 1169 531 949 230 769 182 741 19 588 799 963 553 931 850 1238 459 1264 1222 1273 89 1096 659 1265 479 1182 65 1202 682 958 596 1115 88 841 779 865 571 1223 684 1314 252 704 1192 1204 488 1042 36 741 532 884 75 824 36 934 407 1105 298 1202 698 784 346 927 167 974 788 922 969 988 342 1060 378 655 277 297 159 415 279 694 234 670 963 1216 338 535 28 563 49 584 787 1131 19 323 463 1139 315 930 811 989 202 1244 581 924 126 335 2 30 716 1041 340 850 693 753 130 421 365 1018 67 1215 326 844 476 1023 477 1097 22 669 97 1005 351 552 608 1209 69 148 184 1175 25 506 648 939 923 1288 694 1196 41 95 85 1106 432 1222 853 1256 888 1001 350 709 63 130 753 859 84 1008 298 1278 431 1111 777 1301 292 425 715 1027 274 339 2…
Output: 14

Example 3:

Input: 505 2622 1 505 29 233 225 391 375 442 257 259 196 354 127 502 277 293 346 416 314 316 28 186 362 457 228 367 85 92 259 283 149 291 178 487 283 485 184 231 225 324 20 178 253 335 350 415 28 213 151 301 231 478 15 71 186 255 249 337 133 268 163 487 227 404 129 311 372 492 161 236 276 340 69 211 189 374 300 319 268 272 131 151 140 267 109 270 382 431 133 158 318 475 361 478 114 167 31 79 56 300 148 396 70 152 317 444 70 282 131 405 281 485 354 493 464 495 360 411 94 402 56 479 235 465 145 273 39 214 109 144 89 265 51 424 1 407 183 267 306 337 141 344 220 475 240 358 280 405 196 271 169 429 54 360 179 376 152 398 204 468 264 431 273 333 132 221 48 458 360 432 259 291 288 374 157 410 34 330 183 203 24 45 3 155 91 279 423 492 256 430 198 275 402 473 200 287 348 435 178 219 226 419 200 210 313 36…
Output: 2

Constraints:

1 <= n <= 1382; 0 <= m <= 2764.

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