Problem I
Interconnectivity Measure

There is a city consisting of $n$ junctions and $m$ roads. Each road is numbered from $1$ to $m$. Road $i$ connects junctions $u_ i$ and $v_ i$ bidirectionally. You can travel between any pair of junctions by traveling through the roads.

To travel through roads in the city, you need to buy certain tickets. Ticket $b$ costs $2^ b$ dollars, and it is valid for a single day. You need all tickets $b_1, b_2, \ldots , b_ k$ to travel through road $i$, where $b_1, b_2, \ldots , b_ k$ are the positions of the active bits in the binary representation of $i$. In other words, if $i = 2^{b_1} + 2^{b_2} + \ldots + 2^{b_ k}$ where $0 \leq b_1 < b_2 < \ldots < b_ k$, then you need to have all tickets $b_1, b_2, \ldots , b_ k$ to travel through road $i$. Note that you can reuse the same ticket multiple times within the same day, and it is possible to travel between any pair of junctions within a single day.

You are going to research the interconnectivity measure of the city. Therefore, for the next $q$ days, you are going to travel between a pair of junctions. On the $j$-th day, you are going to travel from junction $s_ j$ to junction $t_ j$, and you want to minimize the cost of tickets you need to buy to travel between these two junctions. Note that you will need to re-buy the tickets for each day.

Input

The first line contains two integers $n$ and $m$, denoting the number of junctions and the number of roads respectively ($1 \leq n \leq 100\, 000$; $n-1 \leq m \leq 100\, 000$).

The next $m$ lines each contain two integers $u_ i$ and $v_ i$, denoting the junctions connected by road $i$ ($1 \leq u_ i \neq v_ i \leq n$). It is guaranteed that you can travel between any pair of junctions by traveling through the roads, and there are no roads which connect the same pair of junctions.

The next line contains a single integer $q$, denoting the number of days you are going to travel between junctions ($1 \leq q \leq 1\, 000\, 000$).

The next $q$ lines each contain two integers $s_ j$ and $t_ j$, denoting the junctions you are going to travel between on the $j$-th day ($1 \leq s_ j, t_ j \leq n$).

Output

Output $q$ lines. The $j$-th line should contain a single integer, denoting the minimum total cost of tickets you need to buy to travel between junctions $s_ j$ and $t_ j$ on the $j$-th day.

Explanation of Sample Input

To travel between junctions $1$ and $5$, the optimal path is to traverse $1 \overset {1}{\Longrightarrow } 3 \overset {2}{\Longrightarrow } 5$. Therefore, you need $2^0 + 2^1 = 3$ dollars.

To travel between junctions $1$ and $4$, the optimal path is to traverse $1 \overset {4}{\Longrightarrow } 5 \overset {2}{\Longrightarrow } 3 \overset {6}{\Longrightarrow } 4$.Therefore, you need $2^1 + 2^2 = 6$ dollars.

6 6
1 3
3 5
1 6
5 1
5 2
3 4
17
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 1
2 1

5
1
6
3
3
5
7
5
7
6
2
3
6
7
3
0
5