# 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.

Sample Input 1 | Sample Output 1 |
---|---|

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 |