← 返回题目列表

AtCoder · code_thanks_festival_2017_h

H. 联合套装

中文机器翻译题面 查看原题

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