Background

During the War of Resistance Against Japan, the tunnel warfare on the Jizhong Plain played an important role.

Problem 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