题目描述

题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T3 「열차의 이동」

调车场是连接或分离列车车厢并进行维护和保养的地方。调车场中有可以移动列车的轨道。我们将用图来表示轨道上列车车厢的位置。图中的每条边表示列车的一个车厢所在的位置，因此列车在图中表示为一条路径。在这条路径上，所有的顶点和边都必须不同。特别地，问题中给出的图总是树形结构。

列车可以沿着轨道移动。列车的移动是分阶段进行的，每个阶段列车的一端车厢移动到相邻的另一条边上。具体来说，对于表示列车的路径 $P$，一次移动的结果是将 $P$ 的一端顶点和相邻的 $P$ 之外的边和顶点添加到 $P$ 中，并将另一端的顶点和边从 $P$ 中移除（见图 1）。注意，每个阶段路径的长度保持不变。

图 1

给定初始和最终列车位置的长度为 $m$ 的路径 $P$ 和 $Q$。路径的长度是路径中包含的边的数量。这里，路径 $P$ 和 $Q$ 之间没有任何共享的边。换句话说，$P$ 和 $Q$ 没有同时经过的边。我们需要将路径 $P$ 移动到最终成为路径 $Q$。此时，需要找到最少的移动步数。

给定包含 $n$ 个顶点的树 $T$ 以及初始和最终列车位置的长度为 $m$ 的路径 $P$ 和 $Q$，编写一个程序，检查是否可以将 $P$ 移动到 $Q$，如果可以，输出最少的移动步数。

例如，在图 2 中，给定长度为 $2$ 的两个路径 $P$ 和 $Q$，它们没有任何共享的边。可以看到，从路径 $P$ 移动到路径 $Q$ 需要 $5$ 步，这是最少的移动步数。

图 2

实现细节

你需要为管理员实现以下两个函数：

void init(int n, vector<int> X, vector<int> Y);

• 该函数在程序开始时调用一次。
• 树的顶点数量为 $n$，顶点编号从 $1$ 到 $n$。
• $X$ 和 $Y$ 是大小为 $n-1$ 的 vector，表示树的每条边为 $(X[i], Y[i])$。

long long train(vector<int> Z);

• 参数 $Z$ 是大小为 $4$ 的 vector，表示初始路径 $P$ 的两个端点 $Z[0]$ 和 $Z[1]$，以及最终路径 $Q$ 的两个端点 $Z[2]$ 和 $Z[3]$。
• 函数返回将 $P$ 移动到 $Q$ 的最少步骤数。如果无法移动，则返回 $-1$。

你需要提交一个名为 train.cpp 的文件，该文件中实现以下两个函数：

void init(int n, vector<int> X, vector<int> Y); long long train(vector<int> Z);

这些函数应按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

示例评测程序

评测程序按以下格式读取输入：

• 第 $1$ 行：$n$ $q$，$n$ 表示树的顶点数量，树的顶点编号从 $1$ 到 $n$，$q$ 表示查询的数量
• 接下来的 $n-1$ 行：$x$ $y$，表示树的一条边 $(x, y)$，$1 \leq x \neq y \leq n$
• 接下来的 $q$ 行：$a$ $b$ $c$ $d$，表示初始路径 $P$ 的两个端点 $a$ 和 $b$，最终路径 $Q$ 的两个端点 $c$ 和 $d$

评测程序将输出函数 train 的返回值。如果无法移动，则输出 $-1$。

样例

输入

11 2
1 2
3 2
4 3
4 5
6 5
8 4
7 8
8 9
10 9
11 10
3 5 7 4
3 6 7 10

输出

3
7

以下是样例中函数调用及其结果的顺序：

函数调用	返回值
init(11, {1,3,4,4,6,8,7,8,10,11}, {2,2,3,5,5,4,8,9,9,10})
train({3,5,7,4})	$3$
train({3,6,7,10})	$7$

数据范围与提示

对于所有输入数据，满足：

• $3 \leq n \leq 2.5\cdot 10^5$
• $1 \leq q \leq 2.5\cdot 10^5$
• 所有查询中路径 $P$ 的长度总和 $\leq 10^6$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	11	$n \leq 80$，$q \leq 80$
2	18	路径 $P$ 的长度 $\leq 2$
3	34	路径 $P$ 的长度 $\leq 100$，所有路径 $P$ 的长度总和 $\leq 2.5\cdot 10^5$
4	36	$n \leq 1,000$，$q \leq 1,000$
5	51	无附加限制