题目描述

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

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

输入

第一行一个正整数 $n$ ，表示结点数量；

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

然后一个整数 $q$ ，表示有 $q$ 个询问；

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

数据范围：

$1≤n,q≤10$^$5$， $1≤x,y≤n$ ；

输出

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

样例

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

3
4