CT41873

The Fewest Hops of Stillwater

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the crane marshes of Stillwater pays by the answer, and Harper intends to earn it. First: the full register of roads. 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: 1150 2067 1 1150 726 993 497 1125 671 896 824 856 719 909 147 558 99 510 65 201 208 500 203 464 217 776 764 985 1008 1066 358 407 53 688 128 555 719 1053 27 255 178 885 765 994 761 841 577 665 167 448 264 1051 37 499 128 620 335 981 521 800 22 147 47 515 751 815 393 570 193 921 412 1050 184 636 133 1131 8 169 431 545 354 588 157 462 128 641 137 280 185 260 397 696 77 616 599 1001 339 858 448 572 746 901 127 989 89 572 699 861 287 1033 581 1007 279 530 57 306 347 947 561 740 159 1005 691 1054 320 1078 421 1147 437 1138 378 814 838 1111 326 490 474 631 298 326 130 898 80 501 293 475 807 827 671 993 1065 1070 86 329 579 664 45 162 370 733 748 820 870 1044 75 569 246 813 384 971 516 545 998 1041 73 393 405 703 565 742 328 1003 371 945 295 912 179 1042 527 1088 623 711 53 432 473 1065 77 469 79…
Output: 6

Example 2:

Input: 151 150 1 151 10 61 22 101 51 57 33 60 67 78 107 128 98 139 8 40 96 98 4 67 42 106 21 76 88 102 79 84 74 75 54 92 6 63 5 89 6 94 2 132 91 128 104 129 12 24 89 117 11 35 9 74 19 89 3 51 47 110 86 151 2 115 44 53 17 83 33 73 53 56 102 131 38 117 42 43 35 148 92 126 10 42 117 124 69 84 57 141 75 80 18 29 16 149 28 48 48 89 46 51 32 65 64 112 34 50 69 80 103 143 78 151 55 127 51 103 33 136 10 83 128 146 26 31 87 117 114 145 24 68 121 137 65 132 2 78 6 27 1 123 49 139 21 127 57 92 75 116 40 77 66 121 84 90 11 59 108 131 24 95 11 41 45 110 16 81 35 114 26 56 69 85 2 150 68 112 31 120 37 126 29 69 30 149 58 89 72 138 10 111 75 89 121 134 61 71 22 92 49 144 21 69 1 85 89 110 27 100 88 117 119 135 21 113 93 114 36 126 119 147 40 135 97 130 14 29 23 40 19 82 25 118 13 141 39 141 57 75 80 130 38 142 …
Output: 8

Example 3:

Input: 38 703 1 38 8 26 27 32 31 36 13 31 19 23 3 35 7 10 1 22 14 34 18 29 5 13 1 32 21 37 2 14 1 18 21 27 14 21 16 20 17 18 16 34 4 26 11 13 2 31 4 12 29 31 20 32 9 27 2 26 3 8 24 27 20 25 7 21 4 31 20 33 17 33 10 25 26 36 21 22 2 35 10 19 14 26 11 23 2 25 9 26 7 37 7 24 1 33 13 17 6 15 7 38 8 22 20 27 31 37 9 25 26 33 8 16 13 22 6 17 28 32 1 21 1 19 9 10 4 18 10 16 1 35 12 34 9 30 4 7 13 25 15 26 10 27 5 30 15 25 1 31 13 32 19 21 15 21 12 23 13 34 23 37 20 26 4 5 32 37 7 30 4 29 2 13 11 24 14 33 5 16 25 28 2 29 1 25 4 35 31 33 26 37 20 30 7 23 1 10 10 34 16 38 11 16 27 30 30 34 33 38 3 5 28 31 1 27 19 38 4 9 24 32 9 38 22 34 19 34 14 15 10 14 15 37 17 28 17 29 19 24 2 27 7 29 8 34 14 25 6 25 14 38 22 24 19 33 16 30 15 17 11 26 6 21 8 12 6 32 32 33 10 20 28 29 9 15 17 21 4 28 7 20 1 17 1 38 23 3…
Output: 1

Constraints:

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

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