Background

Translated from Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D2T2. $\texttt{3s,0.5G}$.

Problem Description

Circle and Flame are playing a game.

There is an undirected graph with $N$ nodes, and Flame will sequentially add $M$ edges to the graph.

Flame has $Q$ queries, each query specifies $u, v$, asking: at least how many edges must be added before $u, v$ are no longer separated by a bridge (in other words, removing any single edge does not affect the connectivity between $u, v$). Specifically, if $u, v$ are never connected or always have a bridge, output $-1$.

Circle is preparing for military training and has asked you to solve this problem.

Input Format

The first line contains two integers $N, M$, as described in the problem statement.

The next $M$ lines, the $i$-th line contains two integers $s_i, t_i$, indicating that the $i$-th edge is $(s_i, t_i)$.

The $(M+2)$-th line contains an integer $Q$, as described in the problem statement.

The next $Q$ lines, each line contains two integers $u, v$, describing a query.

Output Format

Output $Q$ lines, each line containing an integer, representing the answer to the query.

Sample Input and Output

Input Sample #1

3 3
1 2
2 3
3 1
1
1 2

Output Sample #1

3

Input Sample #2

3 4
1 2
1 2
2 3
2 3
3
1 2
2 3
3 1

Output Sample #2

2
4
4

Input Sample #3

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

Output Sample #3

7
5
6
7
-1

Notes

For $100\%$ of the data, it is guaranteed that:

• $2 \le N \le 3 \times 10^5$, $0 \le M \le 3 \times 10^5$, $1 \le Q \le 3 \times 10^5$;
• $s_i \neq t_i$, $u \neq v$;
• $1 \le u, v, s_i, t_i \le N$.

见题面 Input 部分

见题面 Output 部分