配点 : 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