問題文

最初、\{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
• 入力は全て整数である。

入力例 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