AT_pakencamp_2023_day2_h Two PCities

“提升计算机能力之国”有 $N$ 个城市，以及连接这些城市的 $N-1$ 条双向道路。第 $i$ 条道路连接城市 $A_i$ 和 $B_i$。除了道路以外无法在城市之间移动，并且任意两座城市间总可以通过若干道路相连。也就是说，这个国家的城市和道路形成一棵树。 “Pa研国”也有 $N$ 个城市。这个国家中，城市 $a$ 和 $b$（$a \neq b$）之间只有在以下条件成立时且仅在此时才存在道路： - 如果从“提升计算机能力之国”的城市 $a$ 到 $b$ 的最短路径长度不少于 $K$，那么在“Pa研国”的 $a$ 与 $b$ 之间存在一条道路。 现在要回答以下 $Q$ 个问题。第 $i$ 个问题如下： - 仅使用“Pa研国”的道路，能否从城市 $X_i$ 到 $Y_i$ ？如果可以，至少需要经过几条道路？

输入按以下格式从标准输入读入。 > $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$ 行输出第 $i$ 个问题的答案。对于每个问题，如果无法到达则输出 `-1`，否则输出所需经过的道路的最小数量。

### 配点 本题配有以下小任务分数： 1. （$300$ 分）$N, Q \leq 1000$ 2. （$500$ 分）没有额外限制。 ### 样例说明 1 在“提升计算机能力之国”中，城市 $1$ 和 $4$ 的距离为 $3$，所以在“Pa研国”中，城市 $1$ 和 $4$ 之间的距离为 $1$。因此，第 $1$ 个查询输出 `1` 即可。 对于查询 $2$，可以按城市 $2, 4, 1, 3$ 的顺序依次经过即可到达，这已是最优方案，所以输出 `3`。 # 数据范围 - $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)$ - 所有输入均为整数。 由 ChatGPT 5 翻译