CT32077

Eklavya and the Saffron routes

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Caravans arrive at the temple city of Sunspire with crates of routes, and Eklavya the valuer must account for every last one. 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 <= 1316; 0 <= m <= 2632.

Example 1:

Input: 582 1530 1 582 137 361 199 208 191 534 224 537 87 223 314 404 17 382 85 501 63 132 3 390 215 403 54 492 221 446 325 573 305 320 247 575 41 405 273 566 125 448 4 391 54 66 106 455 273 434 107 439 22 364 150 557 155 367 101 280 203 221 187 479 251 430 263 528 477 525 13 449 133 546 55 530 139 148 226 397 18 401 7 384 94 270 301 349 145 538 233 399 68 204 206 540 249 554 23 332 140 326 293 525 35 358 160 460 8 149 64 168 87 93 218 563 337 467 137 349 168 495 216 477 90 418 7 22 97 545 259 394 472 503 33 248 287 417 188 494 365 541 278 480 146 292 75 283 204 389 57 273 24 136 76 374 215 485 471 572 317 507 92 408 85 438 70 98 88 162 266 280 126 335 230 391 148 493 188 273 214 479 214 375 89 320 299 513 306 493 73 191 38 110 92 500 235 431 257 416 253 503 22 333 93 133 287 577 129 335 38 449 22…
Output: 3

Example 2:

Input: 564 1817 1 564 160 427 386 387 62 81 119 563 63 533 222 427 316 432 57 144 249 471 442 556 367 457 155 446 24 320 34 164 312 407 285 535 371 383 309 541 192 514 46 107 201 246 273 296 317 394 355 408 11 176 8 219 5 103 95 485 163 294 114 297 213 467 464 506 340 521 162 467 349 373 24 319 55 281 28 276 81 209 346 378 276 488 26 130 544 549 130 346 208 495 110 473 203 523 110 533 276 375 48 272 140 192 84 261 45 542 66 207 315 494 470 494 456 463 212 525 178 347 186 463 145 242 208 525 54 372 217 509 144 303 108 245 46 234 137 245 1 307 60 412 86 155 99 166 483 496 87 196 151 368 21 206 98 195 418 424 252 482 140 517 272 292 15 215 458 503 190 367 98 367 72 557 97 420 42 557 76 416 216 556 56 122 40 439 53 248 455 459 338 497 114 341 153 369 42 275 279 509 333 548 351 559 269 376 96 192 264 …
Output: 4

Example 3:

Input: 373 1601 1 373 1 148 105 315 44 242 39 206 47 179 191 252 11 84 49 207 27 126 265 334 246 285 10 242 165 241 19 91 45 252 37 335 142 147 17 314 363 371 54 318 234 351 69 355 99 153 35 230 244 344 42 73 188 341 121 164 147 260 52 264 346 372 73 100 252 300 126 202 163 250 75 279 136 255 55 306 49 153 2 110 80 315 174 281 42 255 243 268 4 154 37 268 107 134 292 323 115 134 352 370 237 367 25 285 190 232 210 293 46 187 58 253 195 266 264 367 22 165 162 182 49 372 201 366 166 264 67 190 76 86 70 213 179 226 22 253 9 308 168 189 127 284 3 93 268 344 118 322 54 334 82 287 122 232 93 191 68 77 79 358 113 209 132 246 219 361 11 125 32 281 48 253 69 328 102 117 37 143 199 345 150 238 67 358 111 365 38 76 199 316 125 138 36 282 165 185 7 140 94 303 160 294 29 172 80 240 265 349 49 89 289 303 277 289…
Output: 3

Constraints:

1 <= n <= 1316; 0 <= m <= 2632.

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