Problem Description

Initially, you are given $N$ sets $\{1\}, \{2\}, \ldots, \{N\}$.
After this, $M$ operations of merging sets will be performed.
In the $i$-th operation $(1 \leq i \leq M)$, the set containing element $a_i$ and the set containing element $b_i$ will be merged.
However, if elements $a_i$ and $b_i$ already belong to the same set, nothing happens.

Next, $Q$ query questions are given, and the content of the $j$-th query $(1 \leq j \leq Q)$ is as follows:

• "After which operation will elements $x_j$ and $y_j$ be merged into the same set?"

If after $M$ operations, elements $x_j$ and $y_j$ do not belong to the same set, output -1.
Otherwise, output the smallest $K$ $(1 \leq K \leq M)$ such that after the $K$-th operation, elements $x_j$ and $y_j$ belong to the same set.

Input Format

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

$N$ $M$ $a_1$ $b_1$ $:$ $a_M$ $b_M$ $Q$ $x_1$ $y_1$ $:$ $x_Q$ $y_Q$

Output Format

Output $Q$ lines of answers to the query questions.
The $j$-th line $(1 \leq j \leq Q)$ should contain the answer to the $j$-th query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
2
4
4
-1

Sample Input #2

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

Sample Output #2

2
4
6

Sample Input #3

10 0
5
1 2
4 3
5 6
8 7
9 10

Sample Output #3

-1
-1
-1
-1
-1

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$
• $1 \leq Q \leq 10^5$
• $1 \leq x_j, y_j \leq N$
• $x_j \neq y_j$
• All inputs are integers.

Sample Explanation 1

First, there are 7 sets $\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\}$. After 5 operations of merging sets, the state of the sets after each operation is as follows:
- After the 1st operation: $\{1, 2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\}$
- After the 2nd operation: $\{1, 2\}, \{3, 4\}, \{5\}, \{6\}, \{7\}$
- After the 3rd operation: $\{1, 2\}, \{3, 4\}, \{5\}, \{6\}, \{7\}$
- After the 4th operation: $\{1, 2, 3, 4\}, \{5\}, \{6\}, \{7\}$
- After the 5th operation: $\{1, 2, 3, 4\}, \{5\}, \{6\}, \{7\}$

见题面 Input 部分

见题面 Output 部分