该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一棵包含 $n$ 个节点的树，节点编号为 $1$ 到 $n$。定义树上两条路径 $P_1$ 和 $P_2$ 的距离 $D(P_1, P_2)$ 为：

$D(P_1, P_2) = \min_{u \in P_1, v \in P_2} \text{dist}(u, v)$

其中 $\text{dist}(u, v)$ 表示节点 $u$ 和 $v$ 在树上的最短路径的边权之和。

现在有 $q$ 次询问，每次询问给出两条路径 $P_1$ 和 $P_2$，你需要计算 $D(P_1, P_2)$。

输入格式

第一行包含一个整数 $n$（$2 \leq n \leq 2 \times 10^5$），表示树的节点数。

接下来的 $n-1$ 行，每行包含三个整数 $u, v$（$1 \leq u, v \leq n$），表示节点 $u$ 和 $v$ 之间有一条权值为 $1$ 的边。

接下来一行包含一个整数 $q$（$1 \leq q \leq 2 \times 10^5$），表示询问的次数。

接下来的 $q$ 行，每行描述一个询问，包含四个整数 $a, b, c, d$（$1 \leq a, b, c, d \leq n$），表示两条路径 $P_1$ 和 $P_2$：

• $P_1$ 是节点 $a$ 和 $b$ 之间的最短路径。
• $P_2$ 是节点 $c$ 和 $d$ 之间的最短路径。

输出格式

对于每个询问，输出一行一个整数，表示 $D(P_1, P_2)$ 的值。

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

2
0
0
0
1