#codethanksfestival2017h. [code_thanks_festival_2017_h]Union Sets
[code_thanks_festival_2017_h]Union Sets
问题文
最初，给定了 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≤10^5
- 0≤M≤10^5
- 1≤ai,bi≤N
- ai≠bi
- 1≤Q≤10^5
- 1≤xj,yj≤N
- xj≠yj
- 输入为整数。
输入
输入以以下格式从标准输入中给出。
N M a1 b1 : aM bM Q x1 y1 : xQ yQ
输出
输出 Q 行，表示每个查询的答案。 第 j 行输出第 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 个集合 。 之后，进行了 5 次合并操作，每次操作后集合的状态如下：
- 第 1 次操作后：
- 第 2 次操作后：
- 第 3 次操作后：
- 第 4 次操作后：
- 第 5 次操作后：
输入例子 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