CT30485

Rhys and the Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Legend says the vault under the silver mines of Lodebarrow opens only for a perfect tally of roads. Rhys means to find out. 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 <= 690; 0 <= m <= 1380.

Example 1:

Input: 517 516 1 517 168 360 201 350 330 448 82 199 38 94 123 232 122 183 211 245 92 158 54 257 224 356 87 180 136 462 137 500 12 112 16 164 7 308 62 191 8 58 406 505 162 506 3 261 74 292 390 482 226 330 191 386 97 220 202 491 181 432 272 428 310 485 72 360 20 386 39 143 55 402 326 462 165 330 188 497 159 383 100 140 186 375 254 406 303 330 43 272 20 360 173 232 144 401 55 477 147 276 47 83 276 374 334 451 49 482 120 398 320 453 128 227 144 221 215 263 151 179 216 312 87 201 259 473 169 481 194 380 165 405 185 452 140 205 340 407 167 335 254 413 5 159 56 232 130 167 150 286 141 319 142 425 254 394 344 434 119 277 41 465 406 454 91 262 232 504 45 359 134 201 179 283 314 464 247 306 50 488 185 401 205 371 186 232 96 319 116 482 39 148 189 393 189 354 43 439 147 293 52 280 346 451 33 446 234 275 181…
Output: 8

Example 2:

Input: 150 662 1 150 106 129 64 147 9 65 84 97 44 51 43 134 9 32 87 123 7 35 67 125 42 103 51 71 30 117 97 134 99 148 33 116 9 79 49 52 46 106 1 70 37 80 48 87 106 113 105 121 66 126 76 142 43 85 62 98 28 108 80 133 19 81 45 109 94 117 25 41 21 36 26 120 46 49 39 128 20 37 7 118 112 123 146 150 27 132 43 117 11 147 35 115 73 86 55 68 22 89 18 105 38 123 6 9 83 127 17 110 25 54 39 116 6 71 95 136 74 86 88 134 83 102 45 91 56 79 101 102 17 40 89 123 7 83 12 87 57 91 14 27 63 121 47 119 52 141 66 70 99 117 34 124 33 74 36 79 60 63 37 86 60 61 73 110 28 53 95 126 113 142 72 120 55 72 66 93 36 146 9 113 23 42 10 40 13 79 97 119 68 83 15 143 57 66 32 88 121 135 16 45 11 58 63 145 74 107 42 129 96 103 139 147 59 129 10 77 2 118 92 99 48 59 136 144 86 147 86 91 95 122 105 130 38 140 4 100 32 53 8 27 90 1…
Output: 2

Example 3:

Input: 274 1066 1 274 142 143 126 207 107 262 2 28 9 256 15 117 92 272 179 254 77 174 7 211 13 92 51 129 48 188 77 162 125 251 98 203 70 87 51 239 16 246 77 255 138 157 85 123 217 225 15 106 31 55 148 230 54 237 129 197 247 258 119 126 162 195 24 267 14 179 57 213 57 223 52 221 95 131 254 274 8 255 175 206 91 200 263 266 67 86 150 212 130 247 219 241 97 189 243 271 134 181 104 194 17 163 60 125 232 242 54 261 1 11 53 204 60 139 234 256 148 150 244 265 114 161 161 270 63 106 110 237 148 219 107 147 215 252 24 228 49 193 42 256 66 128 60 202 142 256 116 234 213 229 81 155 138 216 65 100 1 107 34 89 158 231 41 237 29 239 7 9 129 241 52 138 218 248 216 225 20 181 47 183 166 266 30 147 5 211 20 41 8 165 10 28 177 212 175 269 52 161 46 129 167 273 86 156 24 165 11 169 105 264 231 236 152 266 221 222 16…
Output: 3

Constraints:

1 <= n <= 690; 0 <= m <= 1380.

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