Description

Agent 007 has discovered a plot by her greatest enemy, Dr. De Referenced Nullpointer (Dr. Null for short): Dr. Null is going to destroy one of Luogu’s two servers. Dr. Null is about to carry out his plan and is already on the way to the servers. Unfortunately, this means 007 has to say goodbye to her life of having breakfast while chatting up a handsome guy.

Both 007 and Dr. Null have hacked into a satellite system, so they always know each other’s position. The satellite system represents the map as a connected undirected graph. 007, Dr. Null, and the two servers are all located on nodes. In particular, it is guaranteed that the two servers are on two adjacent nodes. Both 007 and Dr. Null can move along one edge in one unit of time, and they may also choose not to move. Dr. Null also needs one unit of time to destroy a server. Dr. Null and 007 take turns to act, with Dr. Null moving first.

If 007 catches Dr. Null (they are on the same node), or if she can guarantee that Dr. Null cannot destroy the servers for an infinite amount of time, then 007 wins.

007 wants to know the latest time she can keep eating breakfast and chatting up the handsome guy, while still ensuring that she will win no matter what strategy Dr. Null uses.

Please help 007 write a program to compute the latest time she can stop eating breakfast in order to ensure victory. Note: while 007 is still eating breakfast, she cannot catch Dr. Null, even if they are on the same node.

Input Format

The first line contains two positive integers $n, m$, representing the number of nodes and edges in the graph.
The second line contains four distinct positive integers $s, d, a, b$, representing 007’s initial position, Dr. Null’s initial position, and the positions of the two servers.
The next $m$ lines each contain two positive integers $u, v$, indicating an edge connecting nodes $u$ and $v$.

Output Format

Output one number in a single line, representing how long 007 can keep eating breakfast at most in order to ensure victory. Specifically, if 007 must act immediately at the beginning, output $0$.
If 007 cannot win no matter what, output $-1$.

6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

1

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4

0

Hint

For all testdata, it is guaranteed that $4 \le n \le 2 \times {10}^5$, $3 \le m \le 6 \times {10}^5$, $1 \le s, d, a, b \le n$ and they are pairwise distinct, and the graph is connected.

Partial scoring: For each subtask, if your program’s output is smaller than the non-negative correct answer by $1$ on at least one test point, and is completely correct on all other test points, then you will receive $30 \%$ of the score for that subtask. Note that if the correct answer is $0$, then outputting $-1$ is also considered this case.

Translated by ChatGPT 5