Description

There are passages connecting multiple stations in the tunnel system, forming a huge network. However, there is also a hidden danger: when the enemy discovers a station, other stations may lose connectivity as a result.

We define a danger coefficient $DF(x,y)$:

For two stations $x$ and $y(x\neq y)$, if we can find a station $z$ such that after $z$ is destroyed by the enemy, $x$ and $y$ become disconnected, then we call $z$ a key point with respect to $x,y$. Accordingly, for any pair of stations $x$ and $y$, the danger coefficient $DF(x,y)$ is defined as the number of key points between these two stations.

Your task is: given the network structure, compute the danger coefficient between two stations.

Input Format

The first line of the input contains $2$ integers $n(2 \le n \le 1000)$ and $m(0 \le m \le 2000)$, representing the number of stations and the number of passages.

The next $m$ lines each contain two integers $u,v(1 \le u,v \le n,u\neq v)$, representing a passage.

The last line contains two numbers $u,v$, representing a query for the danger coefficient $DF(u,v)$ between the two stations.

Output Format

Output one integer. If the two queried stations are not connected, output $-1$.

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

2

Hint

Time limit: 1 second, 64 MB. The 4th Lanqiao Cup National Contest in 2013.

Translated by ChatGPT 5