#codethanksfestival2017h. [code_thanks_festival_2017_h]Union Sets

[code_thanks_festival_2017_h]Union Sets

問題文

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

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

  • 「要素 xjx_j と 要素 yjy_j が同じ集合に併合されるのは何回目の操作後ですか?」

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

制約

  • 2N1052≦N≦10^5
  • 0M1050≦M≦10^5
  • 1ai,biN1≦a_i,b_i≦N
  • aibia_i≠b_i
  • 1Q1051≦Q≦10^5
  • 1xj,yjN1≦x_j,y_j≦N
  • xjyjx_j≠y_j
  • 入力は全て整数である。

入力

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

NN MM a1a_1 b1b_1 :: aMa_M bMb_M QQ x1x_1 y1y_1 :: xQx_Q yQy_Q

出力

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


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

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

  • 11 回目の操作の後 1,2,3,4,5,6,7\\{1,2\\},\\{3\\},\\{4\\},\\{5\\},\\{6\\},\\{7\\}
  • 22 回目の操作の後 1,2,3,4,5,6,7\\{1,2\\},\\{3,4\\},\\{5\\},\\{6\\},\\{7\\}
  • 33 回目の操作の後 1,2,3,4,5,6,7\\{1,2\\},\\{3,4\\},\\{5\\},\\{6\\},\\{7\\}
  • 44 回目の操作の後 1,2,3,4,5,6,7\\{1,2,3,4\\},\\{5\\},\\{6\\},\\{7\\}
  • 55 回目の操作の後 1,2,3,4,5,6,7\\{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