CT29860

The routes at Greyfen

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Legend says the vault under the foggy moor of Greyfen opens only for a perfect tally of routes. Wasim 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 <= 863; 0 <= m <= 1726.

Example 1:

Input: 520 519 1 520 225 271 10 443 114 118 112 509 337 403 13 126 91 94 194 291 132 210 149 391 290 339 273 405 290 406 277 466 222 320 228 447 370 412 117 346 48 132 238 472 268 416 208 500 40 350 115 388 82 388 6 438 276 491 236 299 384 408 50 193 318 517 418 440 172 326 28 420 95 126 118 396 170 303 223 326 293 518 234 339 228 368 369 482 309 404 102 119 7 211 49 139 161 225 116 508 295 390 25 280 158 383 118 334 426 506 47 359 258 319 446 493 61 442 96 517 376 393 402 464 198 373 23 70 54 74 36 361 178 478 197 284 216 228 264 406 241 372 175 207 185 458 223 420 79 516 356 370 160 518 124 256 348 419 271 300 364 481 90 349 132 137 24 65 31 107 219 249 25 513 14 167 215 305 201 372 98 124 113 363 39 327 85 175 46 228 404 476 239 439 188 358 275 429 361 499 134 142 110 376 324 511 467 473 394 427 320 482 3 177 268 477 370 411 192 436 43 209 338 393 69 421 196 319 243 326 31 34 44 74 279 451 44 235 424 487 135 427 208 342 307 372 234 301 268 482 180 499 25 406 21 464 397 415 106 385 57 168 142 328 10 113 31 471 19 513 356 464 254 321 5 133 102 208 12 271 324 461 408 455 136 183 10 97 138 494 239 384 242 430 8 270 105 432 200 353 85 457 155 192 296 393 83 243 436 509 424 479 345 423 32 380 424 463 140 394 147 309 335 460 340 450 51 288 225 298 202 378 68 150 134 468 16 284 128 350 119 428 106 128 220 319 209 303 127 387 287 304 80 457 215 362 251 293 290 490 215 367 110 315 414 494 317 474 70 336 165 490 350 360 71 515 139 484 8 51 113 276 184 387 108 492 201 227 56 128 251 501 77 327 113 400 103 448 28 364 417 464 332 457 229 356 27 203 158 514 42 450 63 264 149 189 257 371 331 386 273 306 393 402 231 348 334 420 232 485 275 410 169 293 71 250 49 335 50 187 33 373 9 364 212 398 220 420 464 498 19 312 82 364 143 417 123 191 101 282 297 444 97 464 215 364 3 503 318 512 39 102 90 409 364 402 101 170 64 266 122 485 85 498 232 432 329 424 270 345 20 214 151 454 185 364 7 157 310 483 466 494 414 508 1 157 275 407 25 38 182 496 286 467 14 144 16 310 224 390 52 262 89 244 176 281 71 202 86 381 98 465 6 362 26 142 175 297 151 385 90 497 321 488 59 213 36 401 76 213 253 436 432 453 456 478 153 364 247 313 69 506 24 284 113 382 31 184 141 392 316 436 51 170 71 420 199 310 311 346 36 506 265 412 241 356 230 386 436 485 304 485 41 516 292 474 163 494 141 170 216 356 169 433 182 331 101 174 171 474 204 383 345 425 452 494 213 486 364 478 335 478 14 317 353 478 32 134 323 381 189 471 15 22 367 413 160 245 266 412 146 341 37 267 169 419 81 364 146 418 448 500 1 254 190 519 74 285 198 489 215 295 98 356 173 353 130 322 195 208 131 470 314 392 30 78 221 394 121 220 251 286 72 131 4 20 308 379 55 113 347 402 186 467 326 472 309 379 11 411 85 482 313 439 404 480 131 402 62 381 272 385 176 188 260 351 69 244 31 67 362 429 159 516 303 355 353 449 417 486 18 481 259 354 273 480 33 152 69 494 162 193 10 233 50 108 215 284 201 366 57 517 98 397 164 454 87 109 422 474 178 462 48 394 119 450 271 309 246 517 340 357 50 85 197 431 48 120 16 511 132 471 32 60 323 475 99 204 158 189 409 495 101 389 71 94 191 419 88 464 132 464 120 145 97 142 261 419 505 517 202 322 111 273 3 27 239 498 243 260 37 393 354 370 2 350 132 373 218 426 205 457 254 402 304 398 235 395 29 437 151 188 279 507 513 520 406 494 207 263 84 156 22 373 324 459 132 436 411 510 18 92 237 263 26 249 365 464 58 337 239 437 90 430 98 257 124 418 217 384 56 104 364 385 9 53 119 434 154 333 84 396 69 208 235 311 235 356 93 133 101 239 138 374 52 278 343 409 399 414 352 399 20 519 248 330 125 390 183 328 45 346 240 305 23 513 181 273 179 442 337 495 226 235 135 504 118 435 137 424 274 385 9 177 182 318 79 229 333 437 66 490 464 518 82 359 330 402 386 441 283 414 100 283 194 520 30 474 23 68 129 172 126 157 75 381 385 517 206 436 157 255 377 383 225 469 69 271 344 452 173 236 166 324 252 319 1 214 87 517 137 294 183 302 275 325 313 502 228 289 106 133 141 451 17 183 69 239 50 278 330 446 223 445 73 397 442 494 269 286 119 375 158 381 142 343 35 316 148 398 98 422
Output: 11

Example 2:

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

Example 3:

Input: 467 563 1 467 195 235 176 414 441 452 317 407 51 459 195 322 117 234 344 411 411 446 302 336 102 107 112 294 191 381 42 271 259 273 203 251 75 294 118 432 233 441 34 363 146 310 107 406 65 99 192 442 233 390 424 464 70 213 155 413 211 234 263 288 418 426 385 416 190 249 295 426 294 345 226 338 35 225 119 264 130 297 27 106 359 423 130 333 69 189 258 318 183 266 316 366 35 197 55 451 216 417 49 272 15 276 239 413 278 461 33 403 61 255 42 260 224 254 155 450 38 315 260 346 58 272 161 276 25 296 32 152 65 290 347 443 75 438 247 315 29 254 323 458 67 394 41 206 255 317 334 367 36 191 7 374 179 190 209 377 140 183 176 404 59 67 68 157 380 464 206 440 129 390 13 330 47 315 62 327 219 457 194 294 272 397 63 248 124 330 73 251 196 290 36 398 128 457 395 421 112 147 10 359 16 381 37 45 261 428 65 176 222 327 157 245 127 233 302 449 28 456 147 256 205 307 217 371 126 188 18 393 23 375 255 350 241 263 211 313 131 442 36 189 217 259 101 317 259 360 134 371 166 360 341 403 125 368 44 406 253 420 343 388 223 311 312 421 41 317 216 322 157 461 161 209 152 399 247 317 127 332 124 356 21 162 57 307 249 404 112 291 286 432 394 413 50 419 242 437 214 317 81 293 86 191 262 412 56 410 93 260 344 370 116 220 65 222 171 242 228 339 38 237 272 450 132 172 80 317 174 234 52 98 343 357 27 154 215 280 142 456 152 239 266 285 91 354 358 412 139 327 211 391 95 139 354 356 15 466 203 323 19 247 73 177 86 323 146 221 191 409 156 266 96 270 22 27 9 245 74 90 13 103 171 358 187 194 393 413 172 286 283 304 102 400 57 58 155 260 35 425 105 399 262 322 93 237 169 313 222 260 61 134 247 292 351 428 163 291 88 236 393 401 320 422 21 72 199 239 109 271 295 321 322 355 151 374 17 174 260 324 2 260 74 95 381 431 398 440 92 263 117 335 63 417 229 467 96 315 175 361 343 430 197 222 4 84 52 192 173 252 55 390 66 394 423 447 416 431 342 373 138 353 53 287 347 459 20 348 309 383 57 326 97 128 30 141 145 265 219 380 320 420 34 375 193 423 130 163 69 349 189 455 161 253 5 192 55 234 403 455 357 446 68 323 170 464 143 180 178 427 45 461 103 433 78 257 150 428 9 309 180 298 116 308 56 162 109 378 60 332 46 262 151 441 48 138 203 365 76 192 110 422 29 281 136 157 238 444 90 451 65 354 222 355 92 349 149 286 264 375 304 402 247 299 182 349 277 376 139 439 218 393 144 205 15 165 38 82 22 33 51 432 61 185 368 394 58 352 322 324 11 65 84 379 108 382 428 465 37 76 207 298 114 290 26 298 133 357 83 369 373 427 379 390 245 291 186 466 92 294 40 181 127 306 313 399 301 396 350 422 164 238 238 428 115 200 121 423 112 311 199 453 205 380 87 375 305 350 191 232 39 187 196 396 153 350 135 137 45 316 209 287 173 178 141 272 47 413 34 463 119 195 260 288 1 381 163 460 334 392 115 193 277 334 113 313 78 97 3 161 165 413 1 386 271 405 98 144 195 317 161 436 309 444 200 325 141 455 206 435 79 404 183 192 40 271 308 315 34 271 204 317 51 448 250 448 159 434 274 372 85 399 14 465 12 421 71 157 284 395 343 381 202 392 203 449 77 93 93 408 212 443 316 444 230 302 156 225 65 69 24 294 176 457 96 140 115 275 55 290 361 460 129 398 343 400 125 433 42 231 132 269 6 142 119 252 3 8 85 244 280 291 163 175 258 449 34 257 378 391 86 232 55 138 423 428 421 433 166 271 38 222 55 238 314 365 43 217 39 402 104 419 158 426 145 167 73 184 83 139 333 454 60 217 246 381 331 444 327 458 282 395 260 419 72 211 9 162 108 322 379 397 152 259 70 210 152 201 245 389 50 374 290 466 166 466 219 321 31 351 9 288 24 413 209 251 76 222 171 293 160 232 302 406 240 280 33 241 229 268 78 175 153 243 174 374 148 380 208 364 122 457 217 376 312 320 168 293 39 381 190 368 83 462 26 262 319 444 255 262 421 427 247 433 58 153 88 89 167 322 110 338 274 290 101 267 397 404 112 173 169 261 29 255 72 222 118 436 159 257 211 236 341 390 69 406 54 68 201 275 122 241 249 279 146 303 226 257 26 239 155 229 128 212 73 150 243 340 94 274 65 118 74 289 74 144 284 456 222 363 46 443 146 241 20 253 25 51 21 262 227 446 248 399 299 445 306 466 4 104 3 208 152 260 131 215 138 188 257 290 301 372 159 449 123 443 431 435 83 100 28 262 198 219 245 253 171 444 101 388 26 214 8 339 64 86 165 277 27 164 291 466 69 297 247 290 252 329 16 111 299 436 225 303 324 386 274 337 27 264 42 362 87 198 33 308 13 329 416 467 179 291 210 408 76 158 240 387 9 300 135 296 65 98 13 429 306 381 384 400 163 265 180 328 93 415 93 120
Output: 4

Constraints:

1 <= n <= 863; 0 <= m <= 1726.

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