题目描述

学校里有 $n$ 间教室，编号从 $1$ 到 $n$。任意两间教室之间要么直接有走廊相连，要么通过若干条走廊间接相通，并且整座教学楼恰好有 $n-1$ 条走廊——也就是说，所有教室和走廊构成了一棵树。两间教室之间的距离定义为它们之间最短路径上的走廊条数。

小 A 和小 B 每天会在不同的教室里上课。放学后，他们想找一个教室一起讨论题目，并且希望这个讨论教室到两人当天所在教室的距离相等。

因为每天的课表都不同，你需要回答接下来 $m$ 天的提问：对于第 $i$ 天，小 A 在 $x_i$ 号教室、小 B 在 $y_i$ 号教室，问有多少间教室 $z$ 满足

$$\operatorname{dist}(z, x_i) = \operatorname{dist}(z, y_i)$$

其中 $\operatorname{dist}(u, v)$ 表示教室 $u$ 与教室 $v$ 之间的距离（边数）。

输入格式

使用标准输入。输入包含多行：

• 第一行一个整数 $n\ (1 \le n \le 10^5)$，表示教室数量。
• 接下来 $n-1$ 行，每行两个整数 $a_j, b_j\ (1 \le a_j, b_j \le n)$，表示第 $j$ 条走廊连接了 $a_j$ 和 $b_j$ 两间教室。
• 接下来一行一个整数 $m\ (1 \le m \le 10^5)$，表示提问的天数。
• 接下来 $m$ 行，第 $i$ 行包含两个整数 $x_i, y_i\ (1 \le x_i, y_i \le n)$，表示第 $i$ 天小 A 和小 B 所在的教室编号。

保证给定的 $n$ 个点与 $n-1$ 条边构成一棵树。

输出格式

使用标准输出。对于每一天输出一行一个整数，表示到小 A、小 B 当天教室距离相等的教室数量。

样例 #1

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

2

样例解释 #1

树的形状为：

    1
    |
    2
   / \
  3   4
      |
      5

第 $1$ 天小 A 在 $3$ 号教室、小 B 在 $4$ 号教室，两人距离为 $2$（路径 $3-2-4$）。逐间检查：

• 教室 $1$：到 $3$ 距离 $2$，到 $4$ 距离 $2$，相等；
• 教室 $2$：到 $3$ 距离 $1$，到 $4$ 距离 $1$，相等；
• 教室 $3$：到自身距离 $0$，到 $4$ 距离 $2$，不等；
• 教室 $4$：到 $3$ 距离 $2$，到自身距离 $0$，不等；
• 教室 $5$：到 $3$ 距离 $3$，到 $4$ 距离 $1$，不等。

共有 $2$ 间教室满足条件。

样例 #2

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

0
1

样例解释 #2

第 $1$ 天两人在 $2$ 和 $5$，距离为 $3$（奇数），不可能存在到两者距离相等的教室，输出 $0$。

第 $2$ 天两人在 $1$ 和 $5$，距离为 $4$（偶数），唯一满足条件的教室是路径正中间的第 $3$ 间，输出 $1$。

数据范围

对于所有数据：$1 \le n \le 10^5$，$1 \le m \le 10^5$，给定的 $n$ 个点与 $n-1$ 条边构成一棵树，$1 \le x_i, y_i \le n$。

本题采用捆绑测试。只有通过一个子任务的全部测试，才能获得该子任务的分数。

子任务	分值	测试点	附加约束
$1$	$20$	$001 \sim 004$	$n \le 100$ 且 $m \le 100$，无依赖
$2$		$005 \sim 008$	$n \le 1000$ 且 $m \le 1000$，无依赖
$3$	$60$	$009 \sim 014$	无附加约束，无依赖

提示

注意两人可能在同一个教室（$x_i = y_i$），此时所有教室都满足条件。