M is the codename of a person who holds one of the key positions in the British Secret Service (MI6). One of the main tasks in this position is the analysis of the security properties of enemy communication networks. This problem outlines one of the typical problems M encounters daily.

The enemy communication network consists of $N$ (seemingly ordinary) post offices and $M$ bidirectional roads that directly connect some pairs of post offices. For simplicity, we will label the post offices with natural numbers from $1$ to $N$.

When the enemy wants to send a secret message from an office labeled $a$ to an office labeled $b$, a secret agent will sit in a fake mail vehicle and drive along some sequence of roads that form a path between those two post offices. A pair of post offices $(a, b)$ is considered vulnerable if there is some road that the secret agent must necessarily pass through on their journey from office $a$ to office $b$, or if there is no path at all between the two offices.

M is currently analyzing the historical vulnerability of one such network. Specifically, M has collected information about the historical development of the network, meaning they know the order in which the roads between the post offices were built. Now, for some pairs of offices, they are interested in the moment (if any) when they ceased to be vulnerable.

Input

The first line contains the numbers $N$ and $M$ from the problem description.

In the $i$-th of the next $M$ lines are $x_i$ and $y_i$, which indicate that the $i$-th built road connected the post offices labeled $x_i$ and $y_i$ ($x_i \neq y_i$).

It is possible that more than one road connects the same pair of post offices.

The next line contains a natural number $Q$, which denotes the number of queries for which M wants to receive an answer.

In the $j$-th of the next $Q$ lines are distinct numbers $a_j$ and $b_j$ that define the $j$-th query of agent M. That is, M wants to find out at what moment the pair of offices $(a_j, b_j)$ ceased to be vulnerable.

Output

In the $j$-th line, you should print the answer to the $j$-th query of agent M.

If the pair of offices from the $j$-th query is still vulnerable, the answer to the $j$-th query is $-1$. Otherwise, the answer is the natural number $k$ which indicates that the pair of offices from the query ceased to be vulnerable after the construction of the $k$-th road.

Subtasks

In all subtasks, $2 \le N \le 300\,000$, $0 \le M \le 300\,000$, and $1 \le Q \le 300\,000$.

Note that in the second subtask, the first two roads connect the same pair of cities, the next two roads connect the same pair of cities, etc.

Examples

Input 1

3 3
1 2
2 3
3 1
1
1 2

Output 1

3

Input 2

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

Output 2

2
4
4

Input 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 3

7
5
6
7
-1

Note

Explanation of the third example: Consider the first query. Up to moment 6 (inclusive), between offices 1 and 3, either no path existed, or every such path passed through road 1. Only at moment 7 is this no longer the case. For the fifth query, a path between offices 2 and 6 never existed, so the answer is -1.