既然你已经利用机器人销售的利润雇佣了一名助手，你终于准备好去寻找装有 CEOI 奖牌的保险箱了！
保险箱位于一栋大学建筑内，该建筑由 $N$ 个房间和 $N-1$ 扇连接它们的门组成。从任何一个房间都可以到达其他任何房间，且每个房间最多有 3 扇门。你和你的助手都拥有该建筑的平面图，但不幸的是，它们是两个不同的版本：虽然两份平面图描述的布局相同，但房间和门的编号可能不同。
在比赛的第二天，组委会将忙于处理澄清请求。这是获取装有奖牌的保险箱的绝佳机会。
起初，你的助手将搜索这栋建筑。一旦他找到了装有保险箱的房间，他就会引导你前往该房间*。由于你不被允许携带手机进入比赛场地，你的助手会在大学的房间里留下秘密标记。为此，他使用了去年 BOI 比赛中剩下的大量领带。由于这些领带无法区分，你唯一能获得的信息就是你的助手在某个房间留下的领带数量。由于一个地方的领带太多可能会引起怀疑，因此任何单个房间内留下的领带数量应尽可能少（见下文评分部分）。
稍后，你会在休息时间溜出去，利用留下的领带找到装有保险箱的房间。请注意，保险箱当然会被隐藏起来，所以你无法通过进入房间来识别它，而必须依赖你找到的领带。此外，由于你的缺席不能被察觉，你必须快速找到保险箱：你通过的门数最多只能是 $d + 30$，其中 $d$ 是从你的起始位置到装有保险箱的房间的最短路径上的门数。如果你多次通过同一扇门，每一次通过都计入总数。
你需要编写一个程序： 告诉你的助手在每个房间留下多少条领带，以及 随后引导你前往装有保险箱的房间。
交互
这是一个交互式任务，你的程序在每个测试点中会被运行两次。你必须实现以下两个函数：
vector<int> mark(vector<pair<int, int>> F, int safe)
其中 $F$ 通过指定门来描述平面图：$F$ 包含 $N-1$ 对 $(u, v)$，满足 $1 \le u, v \le N$ 且 $u \neq v$，这意味着房间 $u$ 和房间 $v$ 之间有一扇门；$safe$ 是装有保险箱的房间。
你的函数应返回一个包含 $N$ 个整数的向量 $T[0], \dots, T[N-1]$，其中 $0 \le T[i] \le 10^9$：$T[i]$ 是你的助手在房间 $i+1$ 中留下的领带数量。$T[i]$ 的数值应尽可能小。
void locate(vector<pair<int, int>> F, int curr, int t)
其中 $F$ 描述了相同的平面图（但房间编号和门的顺序可能不同！），$curr$ 是你当前所在的房间，$t$ 是你在该房间发现的领带数量。
在此函数内部，你可以调用评测库函数 int visit(int v)，以便从你当前的房间移动到房间 $v$（根据你所持平面图版本中的房间编号，$1 \le v \le N$）；该函数返回你的助手在房间 $v$ 中留下的领带数量。房间 $v$ 必须与你当前的房间有门相连，并且你对该函数的调用次数在每个测试点中有限制（见上文）。
当你的 locate 函数返回时，你必须位于装有保险箱的房间内。
对于每个测试点，第一次运行会调用 mark 函数，第二次运行会调用 locate 函数。如果你调用 visit 的次数过多、参数无效，或者在程序第一次运行期间调用，你的提交将被立即终止，并被判为“不正确”（Not correct）。你不得向标准输出写入内容或从标准输入读取内容；否则，你可能会收到“安全违规”（Security violation!）的判决。但你可以自由地向标准错误流（stderr）写入内容。
你必须在源代码中包含 incursion.h 文件。为了在本地测试你的程序，你可以将其与 sample_grader.cpp 链接，该文件可在该任务的附件中找到。请参阅下文了解示例评测库的描述，并查看 sample_grader.cpp 以获取如何将其与你的程序一起运行的说明。请注意，为了简单起见，此示例评测库不会运行你的程序两次，而是作为单次运行的一部分同时调用 mark 和 locate（各一次）。附件中还包含一个示例实现 incursion_sample.cpp。
数据范围与评分
我们始终保证 $2 \le N \le 45\,000$。
- 子任务 1（30 分）：没有房间有 3 扇门。
- 子任务 2（30 分）：恰好有一个房间有 2 扇门。
- 子任务 3（40 分）：无其他限制。
部分评分：在所有子任务中，你的实际得分取决于你的助手在房间中留下的最大领带数量 $T_{\max}$（即 mark 返回值中最大的 $T[i]$），具体如下表所示：
| $T_{\max}$ | $[0, 1]$ | $2$ | $[3, 10^9]$ |
|---|---|---|---|
| 得分 | 100% | 40% | 30% |
样例
考虑一个 $N=3$ 的测试点，其平面图如下：
每个房间中的第一个数字是指你助手的编号，第二个数字是指你自己的编号。保险箱位于底部的大房间（黄色阴影），而你的起始位置在右上角的房间（用粗轮廓绘制）。
在程序的第一次运行中，评测库调用你的函数 mark({{1, 2}, {2, 3}}, 1)。假设这返回 {2, 2, 0}，即你的助手在房间 1 和 2 中各留下了两条领带，而在房间 3 中没有留下领带。
在程序的第二次运行中，评测库调用你的函数 locate({{1, 3}, {2, 3}}, 1, 0)。那么，你的程序与评测库之间的交互可能如下所示：
| 你的程序 | 返回值 | 说明 |
|---|---|---|
visit(3) |
你访问了你编号中的房间 3 | |
| 2 | 这是你助手编号中的房间 2，他在其中留下了两条领带 | |
visit(1) |
（重新）访问你的房间 1... | |
| 0 | ...对应你助手编号中的房间 3，其中没有领带 | |
visit(3) |
（重新）访问你的房间 3... | |
| 2 | ...其中仍然有两条领带 | |
visit(2) |
访问你的房间 2... | |
| 2 | ...对应你助手编号中的房间 1，其中有两条领带 | |
return |
你确定房间 2 包含保险箱，因为这对应于你助手编号中的房间 1，你的程序被判定为正确 |
这里你通过了四扇门，而从你的起始位置到装有保险箱的房间的最短路径上的门数 $d$ 为 2。
此交互过程在 incursion_sample.cpp 中针对公共测试点进行了复现。
评测库
示例评测库首先在标准输入中期望得到整数 $N$ 和 $safe$。之后，它期望得到平面图 $F$，作为 $N-1$ 对整数 $1 \le u, v \le N$ ($u \neq v$) 的序列。
然后它将调用 mark(F, safe) 并将返回值 $T$ 写入标准输出。在此之后，它期望得到你的起始位置 $curr$，并将调用 locate(F, curr, T[curr - 1])；注意，示例评测库不会改变房间和门的编号。然后它会将你程序中所有对 visit 的调用协议写入标准输出。
终止时，示例评测库会向标准输出写入以下消息之一：
Invalid input.：通过标准输入提供给评测库的输入格式不正确。
Invalid call to visit.：你在 mark 中调用了 visit，或者使用了无效参数。
Invalid return value of mark.：mark 的调用没有返回长度为 $N$ 的向量 $T$，或者至少有一个 $T[i]$ 为负数或大于 $10^9$。
Correct: at most Tmax tie(s) per room.：locate 函数在位于 $safe$ 房间时返回，且 $T$ 中的最大值即为 $T_{\max}$。
* Not correct: current position is curr.：locate 函数在位于 $curr \neq safe$ 的房间时返回。
相比之下，实际用于评测你程序的评测库只会输出 Not correct（针对上述任何错误）、Security violation!、Partially correct 或 Correct。此外，评测库是自适应的，即其行为可能取决于你的程序在当前以及之前运行中的操作。无论是示例评测库还是用于评测你程序的评测库，只要发生上述任何错误，都会自动终止你的程序。