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