Agent 007

Agent 007 has uncovered the plan of her old enemy, Dr. De Referenced Nullpointer (Dr. Null for short). Dr. Null wants to pull the power plug of one of two servers. He is already on his way to the server room, so 007 has to leave the man she is having breakfast with at some point.

Both of them have hacked a satellite observation system, so each one always knows where the other is. The system shows the target area as a connected undirected graph. 007, Dr. Null and each of the two servers sit on a node. The two servers stand in one server room, so they sit on two adjacent nodes.

Time is split into time units. In one time unit Dr. Null acts first and 007 acts second.

Dr. Null moves along one edge, stays where he is, or, when a server sits on his node, pulls the plug of that server.

007 moves along one edge or stays where she is. She catches Dr. Null if she stands on his node after her action.

Pulling a plug takes a full time unit, and 007 cannot interrupt it. Once Dr. Null starts to pull, he has done what he came for, and reaching his node in that same time unit is too late.

007 succeeds if she catches Dr. Null, or if she keeps him from ever pulling a plug.

Having breakfast for $T$ time units means that 007 does not act during the first $T$ time units. While she has breakfast she cannot catch anybody, even if Dr. Null stands on her node.

Compute the largest number of time units 007 can spend on breakfast and still be sure to succeed, whatever Dr. Null does.

The first line contains the number of nodes $N$ and the number of edges $M$. Nodes are numbered from $1$ to $N$.

The second line contains four mutually different integers $s$, $d$, $a$, $b$ ($1 \le s, d, a, b \le N$): the starting node of 007, the starting node of Dr. Null, and the nodes of the two servers, in this order.

Each of the next $M$ lines contains two integers $u$ and $v$ ($1 \le u, v \le N$) that describe one edge.

The graph is connected, and node $a$ and node $b$ are joined by an edge.

Print one line with the largest number of time units 007 can spend on breakfast and still be sure to succeed. Print $0$ if she has to leave at the first time unit. Print $-1$ if she cannot succeed at all.

$4 \le N \le 200\,000$, $3 \le M \le 600\,000$.