← 返回题目列表

Codeforces · 418/D

D. 组织者面临的大问题

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

2214年“俄码杯”决赛将在n家酒店举行。两家酒店(假设它们是主要酒店)将举办各种活动,其余酒店将为参与者提供住宿。酒店由 n - 1 条道路连接,您可以从任何一家酒店前往任何一家酒店。

组织者想知道,如果每个参与者都前往距离他最近的主要酒店,并且在由道路连接的两个酒店之间移动需要一个单位时间,那么所有参与者到达主要酒店所需的最短时间是多少。

业主对主要酒店的位置考虑了多种选择。对于每个选项,帮助组织者找到最少的时间。

输入

第一行包含一个整数 n (2 ≤ n ≤ 100000) — 酒店数量。接下来的 n - 1 行每行包含两个整数 - 之间有道路的酒店编号。考虑酒店的编号从 1 到 n。

下一行包含一个整数 m (1 ≤ m ≤ 100000) — 查询数。接下来的 m 行每行包含两个不同的整数——我们假设为主的酒店的编号。

输出

对于组织者的每个请求,打印一个整数 - 所有参与者到达主要酒店所需的时间。

示例

输入 #1

3
2 3
3 1
3
2 1
2 3
3 1

输出 #1

1
1
1

输入 #2

4
1 4
1 2
2 3
3
1 4
1 3
2 3

输出 #2

2
1
2