题目描述

给定一棵n个点构成的树，以及m次询问， 每次给出树上两个点a和b， 求a和b之间的距离为多少（每条边的边权都为1）

输入描述

第一行给定一个整数 $n$,

接下来 $n - 1$ 行，每行给出两个整数 $u, v$，代表 $u, v$ 之间存在一条边

接下来一行给出一个整数 $m$, 代表有 $m$ 次询问

接下来 $m$ 行每行给出两个整数 $a, b$ ，代表一次询问，请你输出 $a$ 点和 $b$点 之间的距离

输出描述

输出一共 $m$ 行， 对于每一个询问单独输出一行，输出 $a, b$ 点之间的距离

样例

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

2
1

数据范围

对于 50% 的测试样例， $1 \le n, m \le 1000$

对于100%的测试样例 $1 \le n, m \le 100000, 1 \le u, v, a, b \le n$