题目描述

给定一棵大小为 $n$ 的树，树上节点编号从 $1$ 到 $n$，树上每条边的长度均为 $1$。

本题中，树上任意两点之间的简单路径长度定义为路径所包含的所有边的长度之和（本题中即为边数）。

很明显，树上任意两点之间存在恰好一条简单路径，现在有 $q$ 次询问，每次询问给定两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n, u_i \neq v_i$），你需要回答出以节点 $u_i$ 为起点，$v_i$ 为终点的简单路径长度。

输入格式

第一行，一个整数 $n(1 \le n \le 2 \times 10^5)$。

接下来 $n-1$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n, x_i \neq y_i$），表示树上一条边连接的两个节点编号。

接下来一行，包含一个整数 $q(1 \le q \le 2 \times 10^5)$，表示询问次数。

记下来 $q$ 行，其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n, u_i \neq v_i$），表示一次询问。

输出格式

对于每次询问的，输出一行，包含一个整数，第 $i$ 个整数表示第 $i$ 次询问对应的从节点 $u_i$ 出发到节点 $v_i$ 的简单路径长度。

样例

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

1
2
3

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,q \le 20$
• 对于 $60\%$ 的数据，$n,q \le 2000$
• 对于 $100\%$ 的数据，$1 \le n,q \le 2 \times 10^5$