题目描述

你用销售机器人的利润雇佣了一名助手，现在你准备好去拿走装有 CEOI 奖章的保险箱了。

保险箱位于一所由 $n$ 个房间所组成的大学建筑内，这些房间由 $n-1$ 扇门连接。每个房间都可以从其他任何房间到达，且每个房间最多与 $3$ 扇门相连。
你和你的助手都有描述建筑物内房间相连情况的平面图，但是你们两个各自拥有的平面图虽然描述了相同的房间结构布局，但是房间和门的编号可能不同。

在比赛的第二天，委员会忙于处理赛时通知和选手提问。这将是接近装着奖牌的保险箱的完美机会。

你的助手会首先搜索整栋大楼。一旦他找到保险箱所在的房间，它就会给你留下前往那个房间的提示。由于手机不能带进赛场，他用了去年 BOI 留下的几乎无限供应的领带。由于这些领带完全相同无法区分，你能获得的信息就是他在任何给定房间里所留下的领带数量。由于一个房间内过多的领带非常可疑，因此任何单个房间内领带的最大数量应当尽可能少（参阅评分部分）。

之后，你计划在上厕所的时候溜出去，利用助手留下来的领带找到有保险箱的房间。保险箱藏在房间里，所以你进入带有保险箱的房间时，必须依靠领带识别这个房间；此外，由于“上厕所”时间过长会被发现，你必须尽快找到保险箱。你最多可以走过 $d+30$ 扇门，其中 $d$ 是你的初始位置到保险箱所在位置的最短路径上的门数量。若重复穿过同一扇门，则每次都计入。

因此，你需要编写一个程序，告诉助手需要在每个房间留下多少条领带，并引导你前往带有保险箱的房间。

输入格式

本题为函数交互题。

对于每个测试点，你的程序会运行两次。

你需要实现如下两个函数（函数原型已给出）：

vector<int> mark(vector<pair<int,int>> F, int safe);

• $F$: 包含了 $n-1$ 个二元组 $(u,v)$，其中 $1 \le u,v \le n$ 并且保证 $u \neq v$，代表在助手的地图上，$u$ 号房间和 $v$号房间之间由一扇门相连。
• $\mathrm{safe}$: 表示你的助手的地图上保险箱所在的房间编号。

该函数应当返回一个长度为 $n$ 的 vector<int> $v$，其中每个元素 $v_i$ 代表你的助手应当在他地图上 $i+1$ 号房间留下的领带数量。你应当保证 $0 \le v_i \le 10^9$。

void locate(vector<pair<int,int>> F,int curr,int t);

• $F$: 包含了 $n-1$ 个二元组 $(u,v)$，其中 $1 \le u,v \le n$ 并且保证 $u \neq v$，代表在你的地图上，$u$ 号房间和 $v$号房间之间由一扇门相连。
• $\mathrm{curr}$: 你目前所在的房间编号。
• $t$: 在你当前所处的房间中，找到的领带数量。

在如下的叙述中，房间编号采用你地图的编号方案。

在实现函数 locate 的过程中，你可以调用如下函数：

int visit(int v);

以此来从你目前所在的房间 $u$ 移动到一个相邻的房间 $v$。你需要保证操作合法，即 $1 \le v \le n,(u,v) \in F\:\vee (v,u) \in F$。

该函数返回一个非负整数 $k$，表示你在房间 $v$ 中找到的领带个数。

该函数调用的次数不应超过 $d+30$，其中 $d$ 是你的起点到终点的最短距离。

当函数 locate 终止时，你应当处于带有保险箱的房间内。

对于每个测试点，第一次运行程序时调用 mark，第二次调用 locate。

如果 visit 调用次数过多、调用不合法或在 mark 中被调用，你的程序将会被终止运行，提交将会被判错误。
你的程序不得写入或读取 stdin 或 stdout，否则将会被判违反安全规定。
但是你可以随便往 stderr 输出，没人管这个。

你需要在源代码文件开头加上 #include "incursion.h"。

你应当将程序与 sample_grader.cpp 链接以进行本地测试。

下面是示例评分器的说明，请参阅 sample_grader.cpp 以获取操作说明。

为简单起见，本评分器不会运行你的程序两次，而是在一次运行中调用两个函数各一次。附件中包含了一个 sample_grader.cpp 的示例实现。

注意：该实现不与评测所用的实现相同，禁止采用 Hack 评分器的方式试图通过本题！

提示

评分细则

共有 4 个 subtask。对于每个测试点，$2 \le n \le 45000$。

Subtask 1 (30 points)，保证没有一个房间有三扇门相连。 Subtask 2 (30 points). 有且仅有一个房间有两扇门相连。 Subtask 3 (40 points). 没有特殊性质。

对于每个测试点，假设使用领带最多的房间用了 $T_{\max}$ 条领带，

• $T_{\max}<2$，你将会获得该测试点 $100\%$ 的分数。
• $T_{\max}=2$，你将会获得该测试点 $40\%$ 的分数。
• $2 < T_{\max} \le 10^9$，你将会获得该测试点 $30\%$ 的分数。

交互库使用方法

注意洛谷提供的交互库与原版不同。

请使用 g++ -std=c++17 -Wall -O2 -o test interactive_lib.cpp xxx.cpp 编译，其中 xxx.cpp 是你的程序名字。

示例交互库首先从标准输入读入三个正整数, $n$, $s$, $seed$，表示点数、起点的原编号、随机数种子。

然后读入 $n-1$ 行，每行两个正整数 $u,v$，表示原树的一条边。其中需保证 $1 \le u < v \le n$。 然后读入一行一个字符串，表示打乱规则。

你不需要在意打乱序号的具体实现。该实现与最终评测所用交互库不一定相同。

接下来交互库将会调用一次 mark，一次 locate。注意交互库可能会打乱序号。

交互库可能向终端输出以下信息：

• Invalid input. 输入不合法。
• Invalid call to visit. (ALICE CALLED VISIT) 在 mark 中调用 visit。
• Invalid call to visit. (INDEX ERROR) 访问了不合法的点。
• Invalid call to visit. (NOT CONNECTED) 访问的点和当前所在的点没有直接的边相连。
• Invalid call to visit. (TOO MANY VISITS) 调用 visit 次数过多。
• Invalid return value of mark. mark 的返回值不合法。即返回的 vector 长度不为 $n$ 或者有小于 $0$ 或大于 $10^9$ 的数。
• Not correct: current position is X 最终并不在目标点，你应该在 $X$ 点（在第二张地图上）。
• Correct: at most X tie(s) per room. 到达目标点，且用领带最多的房间使用了 X 条领带。

最终评测时，只会返回正确与否的信息。