A. Common Edges
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

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

Examples
Input
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
Output
0
1
0
0
Input
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
Output
3
1
5
Note

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.