Minimum Drone Flights

You are given a network of n destinations and m direct bidirectional paths between them. Each path connects two destinations. Your task is to determine the minimum number of drone flights (i.e. the minimum number of edges traversed) required to deliver a package from a starting destination s to a target destination t. If it is impossible to deliver the package, output -1.

The problem can be modeled as finding the shortest path in an undirected graph. The number of flights is equivalent to the shortest distance between s and t. Specifically, if we define the distance using the standard breadth-first search (BFS) algorithm, then the minimum number of flights required is given by:

[ \text{flights}(s, t) = \min_{\text{path } s \to t} ; \text{number of edges in the path} ]

If no such path exists, the answer should be -1.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
u1 v1
...
um vm
s t

Where:

• n: the number of destinations (vertices).
• m: the number of direct paths (edges).
• Each of the next m lines contains two integers u and v denoting a bidirectional path between destination u and v.
• The last line contains two integers s and t, which represent the starting and target destinations respectively.

outputFormat

Output a single integer on standard output (stdout): the minimum number of drone flights required to travel from destination s to destination t. If there is no possible route, output -1.

## sample

5 5
0 1
0 2
1 2
2 3
3 4
0 4

3