CT35000

The Longlegs Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Morning light hits the heron rookery of Longlegs as Jessa unrolls the day's manifest of roads. The tally will decide the next shipment. 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 <= 571; 0 <= m <= 1142.

Example 1:

Input: 348 1082 1 348 36 312 228 314 83 166 11 298 42 337 115 281 46 173 108 319 28 291 34 204 154 219 35 137 217 279 75 90 132 339 283 299 218 246 77 204 68 162 180 223 129 226 38 166 161 214 161 301 128 283 131 161 146 306 102 308 280 287 140 285 291 337 138 146 223 318 77 258 61 293 28 173 172 276 67 278 45 316 142 251 225 237 193 207 9 147 266 291 254 317 251 254 38 169 323 343 8 142 108 118 117 287 55 144 72 113 79 163 212 246 31 142 70 228 285 336 132 145 156 345 65 181 149 198 118 174 174 191 17 290 62 331 250 274 24 297 213 231 200 225 110 144 213 261 144 147 218 329 180 287 268 341 168 309 153 205 94 200 108 165 76 276 91 284 141 217 11 218 45 173 14 69 111 186 221 340 74 320 27 108 147 278 55 129 65 306 109 221 184 251 34 57 68 228 267 272 18 273 212 227 64 254 149 207 81 170 72 298 202…
Output: 3

Example 2:

Input: 560 559 1 560 201 379 54 216 32 366 243 539 190 456 11 379 176 538 8 474 77 393 325 456 19 323 58 99 186 226 18 528 137 549 214 440 389 435 116 210 183 542 81 254 290 544 410 484 100 171 121 272 317 328 32 233 167 263 109 418 248 440 12 160 440 496 274 471 42 540 214 451 62 428 61 256 124 493 116 450 213 457 59 521 70 416 41 334 122 419 133 141 329 509 253 300 357 551 73 187 263 376 477 560 294 520 42 334 162 250 195 255 40 82 268 400 34 209 114 553 3 34 167 439 26 58 72 431 331 350 208 309 70 510 294 395 149 173 282 314 130 372 12 68 69 535 199 351 336 496 108 552 187 486 330 356 421 483 236 314 21 185 142 527 14 180 145 236 217 540 207 532 281 311 90 180 190 252 46 232 407 531 376 461 35 298 203 218 183 227 105 178 281 448 9 512 28 70 120 397 74 225 341 421 293 306 77 284 338 456 145 268…
Output: 12

Example 3:

Input: 221 974 1 221 21 90 92 118 98 131 149 217 147 192 32 190 66 123 15 206 188 197 86 110 98 161 132 192 82 108 90 148 67 101 212 221 123 138 8 171 17 171 2 16 63 90 47 123 68 83 77 111 179 181 127 162 9 116 101 156 69 135 35 181 146 148 144 209 7 179 50 211 36 97 1 72 113 168 39 54 10 162 64 187 79 141 26 117 138 160 94 106 57 108 123 144 21 79 113 197 41 177 2 219 31 57 24 203 5 112 27 161 72 140 36 38 75 166 36 144 47 101 130 198 23 167 108 177 141 161 69 70 169 208 13 89 37 90 59 119 114 215 35 158 79 214 25 189 36 220 46 140 125 192 45 194 86 158 109 125 6 43 64 128 139 204 19 87 88 128 149 175 162 193 75 81 154 206 108 189 123 207 104 198 150 175 180 214 99 115 36 159 145 198 112 121 88 118 22 84 62 152 48 216 97 156 142 201 15 98 4 200 64 216 55 147 141 182 38 175 34 80 118 196 117 164 …
Output: 2

Constraints:

1 <= n <= 571; 0 <= m <= 1142.

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