問題文
最初、1,2,…,N という N 個の集合が与えられます。
この後に、集合を併合する操作が M 回行われます。
時刻 i(1≦i≦M) 回目の操作では 要素 ai を持つ集合と 要素 bi を持つ集合を併合します。
ただし、要素 ai と要素 bi が既に同じ集合に属している場合には何も起こりません。
次に、Q 個の質問クエリが与えられ、j(1≦j≦Q) 番目の質問クエリの内容は以下の通りです。
- 「要素 xj と 要素 yj が同じ集合に併合されるのは何回目の操作後ですか?」
M 回の操作後に 要素 xj と 要素 yj が 同じ集合に属さない場合には、-1
を出力してください。
そうでない場合、K(1≦K≦M) 回目の操作後に要素 xj と 要素 yj が同じ集合に属するので、最小の K を出力してください。
制約
- 2≦N≦105
- 0≦M≦105
- 1≦ai,bi≦N
- ai=bi
- 1≦Q≦105
- 1≦xj,yj≦N
- xj=yj
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M
a1 b1
:
aM bM
Q
x1 y1
:
xQ yQ
出力
質問クエリの解答を Q 行出力せよ。
j(1≦j≦Q) 行目には、j 番目のクエリの答えを出力せよ。
入力例 1
出力例 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
出力例 2
入力例 3
出力例 3