Problem Description

You are given a simple connected undirected graph with $ N $ vertices and $ M $ edges. Here, $M \leq N + 10$.
The vertices are numbered $1, 2, \dots, N$, and the edges are numbered $1, 2, \dots, M$. Edge $ i $ connects vertex $ a_i $ and vertex $ b_i $. The length of every edge is $ 1 $.

Process $ Q $ queries sequentially. The $ i $-th query is as follows:

• Given integers $ u_i $ and $ v_i $. Output the shortest distance between vertex $ u_i $ and vertex $ v_i $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $\vdots$ $ a_M $ $ b_M $ $ Q $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $\vdots$ $ u_Q $ $ v_Q $

Output Format

Output $ Q $ integers according to the instructions in the problem statement, separated by newlines.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
4
1

Sample Input #2

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

Sample Output #2

3
3
2
4
1
1
1
4

Sample Input #3

11 12
6 10
9 10
8 11
3 5
1 8
7 9
2 6
3 6
4 7
3 10
1 7
1 2
6
7 10
3 8
4 7
5 9
4 5
5 10

Sample Output #3

2
4
1
3
5
2

Notes/Hints

Constraints

• All inputs are integers.
• $2 \leq N \leq 10^5$
• $N - 1 \leq M \leq N + 10$
• $1 \leq a_i < b_i \leq N$
• $(a_i, b_i) \neq (a_j, b_j)$ if $i \neq j$
• The given graph is connected.
• $1 \leq Q \leq 10^4$
• $1 \leq u_i < v_i \leq N$

Sample Explanation 1

The given graph is as follows: Therefore,
- The shortest distance between vertex $ 4 $ and vertex $ 6 $ is $ 2 $
- The shortest distance between vertex $ 1 $ and vertex $ 5 $ is $ 4 $
- The shortest distance between vertex $ 1 $ and vertex $ 2 $ is $ 1 $

见题面 Input 部分

见题面 Output 部分