跨国旅行

题目描述

在一棵树上，存在着若干个王国。其中，对于每个度数大于等于 $3$ 的结点， 我们认为这是一个王国的首都。

为了保证公平，王国之间规定领土的划分规则。对于所有的非首都节点，它归属于离它最近的那个首都节点所代表的王国，若有多个，则归属于首都节点编号最小的那个。

现在，小明和小昌有若干条旅行计划想要询问你，每次询问如下：给定你起点 $u$ 和终点 $v$，他们之间的简单路径会跨过多少个不同的王国？

输入格式

输入第一行为一个整数 $n$，表示树的大小。 接下来 $n-1$ 行，每行两个整数 $x,y$，表示树的一条边的两个端点，数据保证构成一颗合法的树。 接下来一行为一个整数 $q$，表示询问次数。 接下来 $q$ 行，每行两个整数 $u,v$，表示询问的两个端点。

数据范围

$n,q \le 2 \times 10^5$ $1 \le x,y,u,v \le n$

输出格式

对于每组询问，每行输出一个整数表示回答。

样例 #1

样例输入 #1

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

样例输出 #1

2
2
1
1