AT_code_thanks_festival_2017_h Union Sets

[problemUrl]: https://atcoder.jp/contests/code-thanks-festival-2017/tasks/code_thanks_festival_2017_h 最初、$ \{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 $ を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 番目のクエリの答えを出力せよ。

### 制約 - $ 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 $ - 入力は全て整数である。 ### Sample Explanation 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\} $