409771: GYM103741 A Common Edges

There is a connected graph with $$$n$$$ vertices and $$$m$$$ undirected edges.

You are given $$$Q$$$ queries, each containing $$$4$$$ integers $$$u,v,x,y$$$. For each query, you need to find one path from $$$u$$$ to $$$x$$$ and another from $$$v$$$ to $$$y$$$, or one path from $$$u$$$ to $$$y$$$ and another from $$$v$$$ to $$$x$$$, so that the common edges between these two paths is the least.

The first line contains two integers $$$n,m\ (2\le n\le 2\cdot 10^5,1\le m\le 3\cdot 10^5)$$$ as described above.

Each of the next $$$m$$$ lines contains two integers $$$u,v\ (1\le u,v\le n)$$$, indicating an undirected edge between $$$u$$$ and $$$v$$$. It is guaranteed that there are no self-loops or multiple edges, and that the graph is connected.

The $$$(m+2)$$$-th line contains an integer $$$Q\ (1\le Q\le 10^5)$$$, the number of queries.

Each of the next $$$Q$$$ lines contains four integers $$$u,v,x,y\ (1\le u,v,x,y\le n)$$$, the starting points and the end points of the two paths.

For each query output an integer in a line, indicating the minimum number of common edges.

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

0
1
0
0

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

3
1
5

In the first example, you can select path $$$(1,2)-(2,3)$$$ and $$$(1,3)$$$ for the first query so that there are no common edges. But in the second query, both paths will pass through $$$(3,4)$$$ so there is at least one common edge.