Agent 007’s Breakfast Dilemma

Agent 007 has uncovered a devious plot by her archenemy, Dr. Null (short for De Referenced Nullpointer). Dr. Null plans to destroy one of the two servers of the LoGu system – and the two servers are located on two adjacent nodes in a connected undirected graph. Both Agent 007 and Dr. Null (as well as the servers) are positioned at nodes on this graph. They move alternately – Dr. Null moves first. In each move an agent can traverse one edge or choose to stay at the current node. In addition, if Dr. Null is at a server node he can spend one move to destroy it. However, while 007 is leisurely having breakfast she cannot intercept Dr. Null even if they land on the same node.

Agent 007 wins if either she eventually catches Dr. Null (i.e. both are at the same node after 007’s move) or she can guarantee that Dr. Null will never be able to destroy a server, no matter how long the game lasts.

Now, 007 (while still enjoying her breakfast) wants to know: What is the maximum number of moves she can afford to delay (i.e. continue her breakfast) yet still be sure to win, regardless of Dr. Null’s strategy?

Assume that once she stops eating, she plays optimally. Note that if she delays too long the head‐start available to Dr. Null might allow him to reach a server and destroy it before she can intercept him.

For analysis, denote by \(d(u,v)\) the shortest-path distance between nodes \(u\) and \(v\) in the graph. Let the two servers be on nodes \(s_1\) and \(s_2\) (which are adjacent, i.e. \(s_1\) and \(s_2\) are connected by an edge). Let 007 start at node \(x\) and Dr. Null at node \(y\). When 007 delays her moves by \(T\) turns, Dr. Null gets to move \(T\) extra times (since he moves first and 007 remains idle during her breakfast). Afterwards, the game becomes a pursuit–evasion race where Dr. Null, aiming to destroy a server, must first travel to one of the servers and then spend one additional move to destroy it. If for at least one server \(s\) it holds that

[ T \le d(y,s) - d(x,s) - 1, ]

then no matter which server Dr. Null chooses (he will pick the option that minimizes \(d(y,s)-d(x,s)-1\)), Agent 007 can still guarantee a win. Hence, the answer is given by

[ T_{\max} = \max\Big(0, \min\big{d(y,s_1)-d(x,s_1)-1,; d(y,s_2)-d(x,s_2)-1\big} \Big). ]

</p>

Your task is to compute \(T_{\max}\) given the graph and the initial positions of the agents and the servers.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of nodes and edges in the graph).

Each of the next \(m\) lines contains two integers \(u\) and \(v\), indicating an undirected edge between nodes \(u\) and \(v\).

The next line contains two integers \(s_1\) and \(s_2\), the nodes where the two servers are located. It is guaranteed that there is an edge between \(s_1\) and \(s_2\).

The last line contains two integers \(x\) and \(y\), representing the starting nodes of Agent 007 and Dr. Null respectively.

All nodes are numbered from 1 to \(n\). The graph is connected and unweighted.

outputFormat

Output a single integer: the maximum number of moves Agent 007 can continue her breakfast while still being guaranteed a winning strategy. If she cannot delay at all, output 0.

sample

2 1
1 2
1 2
1 2

0