Problem J
Closeness Queries

In an undirected graph, we define the distance between two vertices $u$ and $v$ as the minimum length of a sequence of edges starting at $u$ and ending at $v$. Given $Q$ pairs of vertices in the graph, can you for each pair of vertices compute the distance between them?

The $M$ edges of the graph have been chosen using the following method:

for i between 1...M:
    choose a random edge not in the graph
    add the edge to the graph

The $Q$ queries have been chosen using the following method:

for i between 1...Q:
    choose a random pair of distinct vertices

Input

The first line contains the integers $N$ and $M$ ($N = 45\, 000$, $M = 200\, 000$).

The next $M$ lines contains the edges of the graph. Each line consists of two integers $u$ and $v$ ($0 \le u \neq v < N$, the vertices of the edge).

This is followed by a line containing the number of pairs of vertices $Q$ ($1 \le Q \le 10\, 000$).

The next and final $Q$ lines each contains two distinct integers: the name of the vertices in a pair.

Output

For each pair of vertices in the input, output the distance between them.

If there is no path between the vertices, output -1.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.

Note: For group $2$, you can get part of the score. Let the correct distance for a pair be $d$ and your answer be $d’$. If $d’ \le d \le 2d’$ for every query or no path exists (and you give an arbitrary integer answer between $-1$ and $N$), you will receive $20$ points.

5 4
0 1
1 2
2 0
0 3
7
0 1
0 2
0 3
1 2
1 3
2 3
0 4

1
1
1
1
2
2
-1