Problem E
Interplanetary Tunnels

One year ago astronauts Alice and Bob set off to explore the galaxy each going their own way. The time has finally come for them to reunite and share their findings. Luckily they have set up a series of “hyper tunnels” between the planets they’ve visited. Each hyper tunnel consists of two “gates” (one on each planet). Entering a gate will transport them to the corresponding gate instantly! However, using a hyper tunnel costs a fixed amount of energy from their space suit. As such they agree to meet halfway to keep the energy drain as even as possible. Given Alice and Bob’s starting planets and the hyper tunnel system they’ve set up, determine the minimum number of hyper tunnels Alice and Bob will have to take.

Input

The first line will contain 2 space-separated integers $n$ and $m$ $(2 \leq n, m \leq 10\, 000)$ where $n$ is the number of planets connected to the hyper tunnel system and $m$ is the number of hyper tunnels. The second line will contain 2 space-separated integers $p_ A$ and $p_ B$ ($0 \leq p_ A, p_ B < n$, $p_ A \neq p_ B$) which are the planets Alice and Bob start at respectively. The next $m$ lines will contain 2 space-separated integers $p_1$ and $p_2$ ($0 \leq p_1, p_2 < n$, $p_1 \neq p_2$) denoting that there is a hyper tunnel connecting planets $p_1$ and $p_2$. No two hyper tunnels will connect the same pair of planets.

Output

Output a single integer $t$ where $t$ is the larger of the number of hyper tunnels Alice or Bob will take (i.e. if one took 3 tunnels and the other took 4, then $t=4$). It is always possible for them to meet by using the hyper tunnels.

4 3
0 3
0 1
1 2
2 3

2

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

1

7 9
0 6
0 1
0 2
0 3
1 2
1 4
2 4
3 5
4 6
5 6

2