配点 : 800 点
問題文
提高计算机技能的国家 N 城市并将它们连接起来 N - 1 由双向道路组成。路 i 是一座城市 A_i, B_i 。您不能使用道路以外的任何方式在城市之间旅行,并且您可以通过多条道路从任何国家前往任何其他国家。换句话说,这个国家形成了一个树形结构作为图。
公园国也 由 N 城市组成。这个国家的城市 当且仅当满足以下条件时, a, b \ (a \neq b) 之间存在道路:
- 可以提高计算机技能的国家/地区的城市 a, b 之间 K 无法通过少于一条道路行驶。 回答
下面 Q 问题。 第i 题如下。
- 巴基斯坦的城市 是否可以仅使用道路在 X_i, Y_i 之间行驶?如果可以的话,最少需要走多少条路?
制約
- 2 \leq K + 1 \leq N \leq 10^5
- 1 \leq A_i, B_i \leq N \ (1 \leq i \leq N - 1)
- 给定的图是一棵树。
- 1 \leq Q \leq 10^5
- 1 \leq X_i, Y_i \leq N, X_i \neq Y_i \ (1 \leq i \leq N - 1)
- 所有输入均为整数
配点
分数由以下子作业确定。
- (300 点) N, Q \leq 1000
- (500 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
N Q K
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_Q Y_Q
出力
Q 行。i \ (1 \leq i \leq Q) 问题在行
打印 i 的答案。对于每一个问题,如果你不能来回,
打印 -1 ,如果没有,则打印所需的最少道路数。
入力例 1
4 2 2 1 2 2 3 3 4 1 4 2 3
出力例 1
1 3
提高计算机技能的国家/地区的城市 1, 4 的距离是
给出 3 因此,帕肯国家的城市 1, 4 的距离是
给出 1 。因此,查询
只需输出 1 中
由于 1 。
查询 2 对于城市
您可以按照步骤 2, 4, 1, 3 进行移动。因为这是最好的
输出 3 。
我锻炼
入力例 2
7 3 3 1 2 1 3 2 4 2 5 3 6 3 7 3 4 2 3 6 7
出力例 2
1 3 2