CODE THANKS FESTIVAL 2017

H - Union Sets


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 600

問題文

最初、\{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

Submit提出する