2399 - 树上的距离

题目描述

给定一棵树,树上有 n 个结点,结点编号为 1 \sim n

再给定 q 次询问,每次询问给定 2 个结点编号,请编程计算出这两个结点在树上的距离。

输入

第一行一个正整数 n,表示结点数量;

接下来 n−1 行,每行两个整数 x,y 表示 x,y 之间有一条连边;

然后一个整数 q,表示有 q 个询问;

接下来 q 行每行两个整数 x,y 表示询问 xy 的距离。

数据范围:

1≤n,q≤1051≤x,y≤n

输出

输出 q 行,每行一个整数,表示每次询问的答案。

样例

输入

6
1 2
1 3
2 4
2 5
3 6
2
2 6
5 6

输出

3
4
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题