在 IOI 王国中，有 $N$ 座城市，编号从 $0$ 到 $N-1$。这些城市由 $N-1$ 条道路连接，道路是双向的。你可以通过这些道路从任意城市到达其他任何城市。
在 IOI 王国中，有许多生产特殊组件的公司。每家公司只生产一种组件。没有两家公司生产同一种组件。每家公司至少拥有一家工厂。每家工厂都建在某座城市中。同一座城市中可能有多家公司的工厂。
有时，一家公司需要另一家公司的组件。假设公司 $C_A$ 需要公司 $C_B$ ($C_A \neq C_B$) 的组件。在这种情况下，他们需要将组件从 $C_B$ 运输到 $C_A$。他们可以将组件从公司 $C_B$ 的任意一家工厂运输到公司 $C_A$ 的任意一家工厂。他们需要适当地选择工厂，以使工厂之间的距离最小。
题目描述
首先，给定 IOI 王国的城市数量和道路信息。然后，给定 $Q$ 次查询。 每次查询的形式如下：公司 $U_j$ 在城市 $X_{j,0}, \dots, X_{j,S_j-1}$ 拥有工厂，需要公司 $V_j$ 在城市 $Y_{j,0}, \dots, Y_{j,T_j-1}$ 的组件。编写一个程序，对于每次查询，返回运输组件的最小距离。
实现细节
你需要编写一个程序来实现处理查询的过程。
你的程序应包含头文件 factories.h，即使用 #include "factories.h"。
你的程序应实现以下过程：
void Init(int N, int A[], int B[], int D[])此过程在开始时仅调用一次。参数 $N$ 是 IOI 王国的城市数量。参数 $A$、$B$ 和 $D$ 是长度为 $N-1$ 的数组。元素 $A[i]$、$B[i]$ 和 $D[i]$ 分别是三个整数 $A_i$、$B_i$ 和 $D_i$ ($0 \le i \le N-2$)。这意味着对于每个 $i$ ($0 \le i \le N-2$)，有一条长度为 $D_i$ 的道路连接城市 $A_i$ 和城市 $B_i$。long long Query(int S, int X[], int T, int Y[])此过程针对 $Q$ 次查询中的每一次调用。在查询 $j$ 中，参数 $S$ 和 $T$ 分别是两个整数 $S_j$ 和 $T_j$。它们分别是公司 $U_j$ 和 $V_j$ 拥有工厂的城市数量。参数 $X$ 是一个长度为 $S_j$ 的数组。公司 $U_j$ 在城市 $X[0], X[1], \dots, X[S-1]$ 拥有工厂。参数 $Y$ 是一个长度为 $T_j$ 的数组。公司 $V_j$ 在城市 $Y[0], Y[1], \dots, Y[T-1]$ 拥有工厂。 此过程应返回将组件从公司 $V_j$ 运输到公司 $U_j$ 的最小距离。
编译与运行
你可以从竞赛网页下载包含样例评测程序的压缩包。该压缩包还包含你的程序的样例源文件。
样例评测程序由一个源文件组成，即 grader.c 或 grader.cpp。例如，如果你的程序是 factories.c 或 factories.cpp，你可以运行以下命令来编译你的程序：
C
gcc -O2 -std=c11 -o grader grader.c factories.c -lmC++
g++ -O2 -std=c++11 -o grader grader.cpp factories.cpp
编译成功后，将生成可执行文件 grader。
注意，实际的评测程序与样例评测程序不同。样例评测程序将作为一个单一进程执行，它将从标准输入读取数据并将结果写入标准输出。
样例评测程序的输入
样例评测程序从标准输入读取以下数据：
- 第一行包含两个空格分隔的整数 $N, Q$，表示 IOI 王国有 $N$ 座城市，且有 $Q$ 次查询。
- 接下来的 $N-1$ 行中，第 $(i+1)$ 行 ($0 \le i \le N-2$) 包含三个空格分隔的整数 $A_i, B_i, D_i$，表示有一条长度为 $D_i$ 的道路连接城市 $A_i$ 和城市 $B_i$。
- 第 $j$ 次查询的信息（$0 \le j \le Q-1$）写在接下来的 $3Q$ 行中，从第 $(3j+1)$ 行到第 $(3j+3)$ 行： 第 $(3j+1)$ 行 ($0 \le j \le Q-1$) 包含两个空格分隔的整数 $S_j$ 和 $T_j$ ($1 \le S_j \le N-1, 1 \le T_j \le N-1$)，表示公司 $U_j$ 和 $V_j$ 分别在 $S_j$ 和 $T_j$ 座城市拥有工厂。 第 $(3j+2)$ 行 ($0 \le j \le Q-1$) 包含 $S_j$ 个空格分隔的整数 $X_{j,0}, \dots, X_{j,S_j-1}$，表示公司 $U_j$ 在这些城市拥有工厂。 第 $(3j+3)$ 行 ($0 \le j \le Q-1$) 包含 $T_j$ 个空格分隔的整数 $Y_{j,0}, \dots, Y_{j,T_j-1}$，表示公司 $V_j$ 在这些城市拥有工厂。
样例评测程序的输出
当程序成功终止时，样例评测程序会将 Query 返回的值写入标准输出，每行一个。
数据范围
所有输入数据满足以下条件：
- $2 \le N \le 500\,000$。
- $1 \le Q \le 100\,000$。
- $0 \le A_i \le N-1$ ($0 \le i \le N-2$)。
- $0 \le B_i \le N-1$ ($0 \le i \le N-2$)。
- $1 \le D_i \le 100\,000\,000$ ($0 \le i \le N-2$)。
- $A_i \neq B_i$ ($1 \le i \le N-2$)。
- 你可以通过这些道路从任意城市到达其他任何城市。
- $1 \le S_j \le N-1$ ($0 \le j \le Q-1$)。
- $0 \le X_{j,k} \le N-1$ ($0 \le j \le Q-1, 0 \le k \le S_j-1$)。
- $1 \le T_j \le N-1$ ($0 \le j \le Q-1$)。
- $0 \le Y_{j,k} \le N-1$ ($0 \le j \le Q-1, 0 \le k \le T_j-1$)。
- $X_{j,0}, X_{j,1}, \dots, X_{j,S_j-1}, Y_{j,0}, Y_{j,1}, \dots, Y_{j,T_j-1}$ 互不相同 ($0 \le j \le Q-1$)。
- $S_0 + S_1 + \dots + S_{Q-1} \le 1\,000\,000$。
- $T_0 + T_1 + \dots + T_{Q-1} \le 1\,000\,000$。
子任务
子任务 1 [15 分]
满足以下条件： $N \le 5\,000$。 $Q \le 5\,000$。
子任务 2 [18 分]
满足以下条件： $S_i \le 10$ ($0 \le i \le Q-1$)。 $T_i \le 10$ ($0 \le i \le Q-1$)。
子任务 3 [67 分]
无附加限制。
样例
输入格式 1
7 3 0 1 4 1 2 4 2 3 5 2 4 6 4 5 5 1 6 3 2 2 0 6 3 4 3 2 0 1 3 4 6 1 1 2 5
输出格式 1
12 3 11
说明
- 在查询 0 中，公司 $U_0$ 在城市 0, 6 拥有工厂，公司 $V_0$ 在城市 3, 4 拥有工厂。从公司 $V_0$ 在城市 3 的工厂到公司 $U_0$ 在城市 6 的工厂距离最小。最小距离为 12。
- 在查询 1 中，公司 $U_1$ 在城市 0, 1, 3 拥有工厂，公司 $V_1$ 在城市 4, 6 拥有工厂。从公司 $V_1$ 在城市 6 的工厂到公司 $U_1$ 在城市 1 的工厂距离最小。最小距离为 3。
- 在查询 2 中，公司 $U_2$ 在城市 2 拥有工厂，公司 $V_2$ 在城市 5 拥有工厂。从公司 $V_2$ 在城市 5 的工厂到公司 $U_2$ 在城市 2 的工厂距离最小。最小距离为 11。