Almost shortest path

Undirected unweighted graph is given. Two vertices s and t are given. Let the shortest path from s to t be d. Almost shortest path from s to t is a path of minimum length that does not contain any edge along which a path of length d can pass. Find the length of the almost shortest path or print -1 if such path does not exist.

Input

First line contains four integers: number of vertices n, number of edges m (n, m ≤ 10^5) and numbers of vertices s and t (1 ≤ s, t ≤ n). Each of the next m lines contain two integers a and b that describe an undirected edge (a, b).

Output

Print the length of the almost shortest path between the vertices s and t. If such path does not exist, print -1.

Examples

Note

The shortest path between vertices 1 and 3 equals to 2. The edges that the shortest path can go through are highlighted in red. Almost shortest path is the shortest path that does not go along any of the red edges. The almost shortest path is highlighted in blue, its length is 5.