题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码：

#include <vector>

void init(int N, std::vector<int> X, std::vector<int> Y);

long long train(std::vector<int> Z);
  

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

题目描述

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

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

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

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

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

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

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。

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

输入格式

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

• 第 $1$ 行：$n\,q$，$n$ 表示树的顶点数量，树的顶点编号从 $1$ 到 $n$，$q$ 表示查询的数量
• 接下来的 $n-1$ 行：$x\,y$，表示树的一条边 $(x, y)$，$1 \le x \neq y \le 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

提示

样例说明 #1

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

函数调用	返回值
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\times 10^5$
• $1 \leq q \leq 2.5\times 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\times 10^5$
$4$	$36$	$n \leq 1000, q \leq 1000$
$5$	$51$	无附加限制

本题满分为 $150$ 分。