問題文

最初、$\\{1\\},\\{2\\},…,\\{N\\}$ という $N$ 個の集合が与えられます。
この後に、集合を併合する操作が $M$ 回行われます。
時刻 $i(1≦i≦M)$ 回目の操作では 要素 $a_i$ を持つ集合と 要素 $b_i$ を持つ集合を併合します。
ただし、要素 $a_i$ と要素 $b_i$ が既に同じ集合に属している場合には何も起こりません。

次に、$Q$ 個の質問クエリが与えられ、$j(1≦j≦Q)$ 番目の質問クエリの内容は以下の通りです。

• ｢要素 $x_j$ と 要素 $y_j$ が同じ集合に併合されるのは何回目の操作後ですか?｣

$M$ 回の操作後に 要素 $x_j$ と 要素 $y_j$ が 同じ集合に属さない場合には、-1 を出力してください。
そうでない場合、$K(1≦K≦M)$ 回目の操作後に要素 $x_j$ と 要素 $y_j$ が同じ集合に属するので、最小の $K$ を出力してください。

制約

• $2≦N≦10^5$
• $0≦M≦10^5$
• $1≦a_i,b_i≦N$
• $a_i≠b_i$
• $1≦Q≦10^5$
• $1≦x_j,y_j≦N$
• $x_j≠y_j$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

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

出力

質問クエリの解答を $Q$ 行出力せよ。
$j(1≦j≦Q)$ 行目には、$j$ 番目のクエリの答えを出力せよ。

入力例 1

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

出力例 1

1
2
4
4
-1

まず、$7$ つの集合 $\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\},\\{6\\},\\{7\\}$ があります。
この後に、集合を併合する操作が $5$ 回あり、各操作の後の集合の状態は以下の通りです。

• $1$ 回目の操作の後 $\\{1,2\\},\\{3\\},\\{4\\},\\{5\\},\\{6\\},\\{7\\}$
• $2$ 回目の操作の後 $\\{1,2\\},\\{3,4\\},\\{5\\},\\{6\\},\\{7\\}$
• $3$ 回目の操作の後 $\\{1,2\\},\\{3,4\\},\\{5\\},\\{6\\},\\{7\\}$
• $4$ 回目の操作の後 $\\{1,2,3,4\\},\\{5\\},\\{6\\},\\{7\\}$
• $5$ 回目の操作の後 $\\{1,2,3,4\\},\\{5\\},\\{6\\},\\{7\\}$

入力例 2

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

出力例 2

2
4
6

入力例 3

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

出力例 3

-1
-1
-1
-1
-1