CT33221

The Quiet Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

At the frontier camp of Duskwood, Scribe records each routes in a worn leather ledger. The guild wants answers, not guesses. 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 <= 549; 0 <= m <= 1098.

Example 1:

Input: 517 1083 1 517 342 411 106 395 65 93 374 440 173 433 151 206 202 286 54 168 180 254 275 514 105 368 142 243 254 265 241 496 99 156 237 357 290 352 124 494 170 221 370 496 77 99 105 437 248 431 254 423 15 431 119 159 123 199 87 179 212 391 45 380 77 189 333 369 312 458 193 365 428 476 180 219 268 270 185 477 165 432 229 322 138 146 28 492 291 301 48 407 22 144 390 493 307 331 65 320 126 308 81 152 150 244 77 382 116 288 178 507 203 305 295 388 15 33 197 422 316 503 115 306 353 403 20 402 120 137 373 498 60 87 170 204 74 239 202 308 348 350 168 302 224 423 2 210 11 46 88 477 132 460 12 36 291 348 228 374 200 205 4 95 177 274 181 446 273 362 19 88 111 268 417 431 16 67 305 465 12 184 153 495 336 514 252 258 75 513 465 494 117 510 5 303 10 80 279 344 446 480 76 85 476 515 70 133 365 408 172 49…
Output: 5

Example 2:

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

Example 3:

Input: 321 684 1 321 218 222 294 314 109 274 232 317 142 217 146 256 174 321 226 250 110 259 39 90 277 313 121 186 12 19 55 250 8 155 273 306 126 313 212 266 166 247 49 290 74 250 238 281 110 195 30 153 157 273 15 128 174 313 18 55 40 100 124 187 131 291 37 148 26 318 96 188 16 280 240 278 60 70 123 236 99 200 115 206 87 110 56 194 206 303 127 139 7 271 158 255 213 221 175 241 46 109 222 293 101 104 14 119 52 262 38 71 171 218 2 166 33 231 142 261 45 86 150 170 13 177 54 181 239 277 16 23 17 216 126 291 178 298 10 249 18 196 155 274 35 205 25 138 140 182 101 193 35 60 105 220 117 215 197 317 52 157 162 229 143 170 14 307 116 231 14 240 202 240 29 170 221 237 4 5 9 170 28 210 82 273 119 286 71 115 172 253 91 148 108 280 108 276 54 156 268 291 111 284 239 285 70 196 46 157 17 45 117 269 118 280 5 2…
Output: 4

Constraints:

1 <= n <= 549; 0 <= m <= 1098.

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