← 返回题目列表

AtCoder · pakencamp_2023_day2_h

H. 两个 PCity

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

配点 : 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)
  • 所有输入均为整数

配点

分数由以下子作业确定。

  1. (300 点) N, Q \leq 1000
  2. (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