CT41463

The Glowtide Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the lantern reef of Glowtide, Aria the valuer keeps careful count of the canals. Settle a dispute between crews, every figure matters. 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 <= 1333; 0 <= m <= 2666.

Example 1:

Input: 1312 1311 1 1312 904 935 263 617 367 891 586 643 409 1299 111 1216 297 972 839 1010 320 1167 1006 1040 491 1118 471 1061 133 1188 15 89 619 880 71 633 297 1064 332 494 32 383 440 472 850 1040 885 1061 205 353 697 700 520 973 133 279 110 1109 89 626 469 884 1071 1236 1042 1167 97 257 781 897 726 1004 210 934 352 1188 294 1292 740 773 41 413 505 701 143 190 419 683 710 1274 150 590 455 1065 145 176 337 403 137 1134 545 1115 218 1299 451 1208 171 667 722 1063 64 612 758 968 174 282 546 774 259 655 671 1125 901 1110 484 608 102 1170 228 792 181 566 204 378 206 904 156 244 204 255 507 651 686 908 521 863 349 410 13 1277 307 378 853 922 73 797 881 1094 683 1154 418 1150 199 741 382 1110 601 1153 90 639 771 1074 718 1040 408 652 984 995 283 943 995 1147 543 719 583 1235 217 1031 336 970 386 429 4…
Output: 13

Example 2:

Input: 184 2603 1 184 96 99 16 144 125 132 30 40 4 74 20 82 14 56 40 80 30 146 104 176 72 127 23 112 19 118 38 102 59 81 49 152 100 103 131 173 159 180 16 152 21 100 82 111 50 110 99 122 34 153 87 124 10 46 32 84 80 140 54 139 131 149 64 76 110 177 45 136 40 102 6 102 168 184 15 176 138 171 44 160 99 172 24 76 17 44 36 171 45 80 48 50 6 78 68 120 8 77 53 184 1 52 22 132 10 153 44 161 4 157 24 70 69 71 32 85 16 83 59 141 148 165 15 150 87 171 106 169 77 143 147 161 74 167 59 72 2 89 53 69 103 109 51 66 121 159 11 142 118 182 99 161 4 89 38 144 14 178 126 149 110 179 62 160 45 96 115 179 5 18 50 135 57 123 87 141 43 163 102 142 1 136 61 149 102 184 6 23 44 86 19 104 6 37 44 151 62 182 37 162 105 150 158 172 91 152 60 134 40 147 34 43 56 75 99 142 66 160 63 156 19 117 102 150 107 126 19 178 93 123 5…
Output: 2

Example 3:

Input: 241 2436 1 241 73 138 170 237 27 216 132 163 93 130 16 60 116 140 22 167 224 234 118 183 227 228 46 80 85 136 15 172 8 106 119 191 115 139 60 207 56 228 14 150 32 236 103 218 54 195 35 125 98 206 5 59 76 103 54 130 21 200 101 121 12 172 103 207 53 84 21 110 113 216 62 102 113 134 106 199 36 77 59 194 28 85 108 216 169 179 194 234 146 221 66 153 185 213 74 138 40 172 73 99 190 235 44 176 127 157 27 139 44 126 23 163 54 227 224 241 20 219 56 130 114 207 34 182 91 150 125 201 55 182 18 38 87 217 168 232 6 25 31 180 93 143 15 153 119 209 61 122 190 206 81 190 40 154 76 180 173 182 140 166 122 161 21 35 132 192 122 217 6 160 10 87 191 193 45 102 144 170 3 67 135 241 168 229 159 236 42 169 155 215 156 240 55 180 27 64 127 224 108 240 26 232 198 228 168 183 98 211 44 232 28 129 123 130 104 159 20…
Output: 3

Constraints:

1 <= n <= 1333; 0 <= m <= 2666.

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