题目描述

这是一道交互题。

传说，A 市是一座拥有独一无二城市景观和旅游资源的国际化大都市。前些年里，A 市大力发展城市绿化，在城中植树造林。经过不懈努力，城市的每一个角落都已经点缀得绿树成荫。

可正在这风光无限的时刻，突然爆出一系列事件，A 市原本的绿化负责人不见了踪影，绿化项目也被紧急叫停。

但 A 市怎会放过这难得的商机？既然真实的树不让种了，虚拟的树总管不着吧？于是，A 市开通了自己的网站，每一位来 A 市旅游的游客，都可以登录网站并亲手种下一棵独一无二的虚拟树。以后登录网站的游客，也可以将先前他人种下的虚拟树当作城市景观的一部分来观赏。

时间一长，网站上的虚拟树和游客多了起来，网站开始对浏览者收取费用：每次需要花费1元才能观赏到一棵虚拟树。但这仍然阻挡不住游客的热情，于是网站进一步提高了收费标准：每次付费只能观赏到某棵虚拟树的一个局部。

具体来说，现在有一棵 $n$ 个节点的虚拟树，根是 $1$ 号节点。游客每次花费 $1$ 元，可以观赏到树上的任意两个由游客自己指定的节点。在观赏的过程中，游客可以得知这两个点在树上的距离（即连接两点的简单路径所经的边数）。

你作为一名慕名而来的游客，还是希望观赏到一棵完整的虚拟树，于是你打算进行多次“观赏两个节点”的操作来实现这一目标。当然，由于你身上带的钱不多，你希望自己观赏的次数越少越好。

你选中了一棵虚拟树正打算进行观赏，这时突然收到了管理员的消息，告诉你运气不错，选中了 A 市的“特色树”！这种树的与众不同之处在于，每个节点的子节点均不超过 $2$ 个。

这对你当然是个好消息，又能省下一大笔钱了！那么，接下来就看你的了！

实现细节

你不需要，也不应该实现主函数，你只需要实现函数：

void findtree(int n, int m, int* p);

其中 $n$ 是树的节点数，$m$ 是你最多能观赏的次数，$p$ 数组初始均为 $0$，你要用它来返回这棵树的信息。

你可以访问并修改 $p_1\sim p_n$，在该函数运行结束时，$p_i(1\le i\le n)$ 应该表示节点 $1$ 的父节点的编号，特别地 $p_1$ 应该为 $0$。

注意：你不能访问或修改 $p$ 数组的其他位置，否则可能出现意想不到的错误。

你可以调用函数：

int visit(int x, int y);

其中你应保证 $1\le x,y\le n(x\not=y)$，表示你一次观赏的两个节点的编号；函数返回这两个节点在树上的距离。

如何测试你的程序

在提交的时候，请在开头加上 #include "grader.cpp"。

你需要在本地将自己的程序命名为 green.cpp，其中包含你编写的 findtree 函数。

将下发的交互库 grader.cpp 放到你的程序所在的文件夹中，然后编译运行 grader.cpp 即可。

可执行文件将从标准输入读入以下格式的数据：

• 第 $1$ 行：两个正整数 $n,m$。
• 第 $2$ 行：$n$ 个正整数，表示每个节点的父节点的编号，必须是一棵符合题目要求的树，且以 $1$ 号点为根。

如果输入数据符合要求，且你的程序返回了正确的 $p$ 数组，可执行文件会输出：

correct!
tot visit(s): x

其中 $x$ 是你调用 visit 函数的次数。

否则，将输出相应的错误信息。

当然，如果你需要在本地进行文件输入输出操作，你可以通过适当修改 grader.cpp 来实现。

样例

4 6
0 1 4 1

correct!
tot visit(s): 5

这是使用 grader.cpp 和能够正确运行并输出答案的源程序得到的可能输出文件。

对于此样例，一种可能的 visit 函数的调用顺序为：

visit(1,2)，返回1；
visit(1,3)，返回2；
visit(1,4)，返回1；
visit(3,2)，返回3；
visit(3,4)，返回1；

数据范围与评分标准

本题共 $6$ 个子任务，每个子任务由多个测试点组成，你必须通过一个子任务的所有测试点才能通过该子任务。

对于每一个测试点，你只有以符合题目要求的形式调用 visit 函数并正确返回 $p$ 数组才能获得满分；否则，如果你的程序不能正常结束，或者没有返回正确的 $p$ 数组，或者调用 visit 函数的次数超过 $m$，或者调用 visit 函数的参数不合法，将得 $0$ 分。

各个子任务的分值和数据范围如下：

子任务编号	分值	$n=$	$m=$
$1$	$10$	$10^3$	$5\times 10^5$
$2$	$15$	$3\times 10^3$	$6\times 10^5$
$3$	$20$	$10^4$	$10^6$
$4$	$15$	$3\times 10^4$	$2\times 10^6$
$5$	$15$​	$5\times 10^4$	$3\times 10^6$
$6$	$25$	$10^5$	$5\times 10^6$

对于所有的测试点，保证 $1\le n\le 10^5$，$1\le m\le 5\times 10^6$，给出的树符合题目要求。

注意事项

本题时限 $2s$，空间限制 $512MB$。保证对于任何合法的数据及在限制范围内的调用，交互库运行所用的时间不会超过 $0.5s$，运行所用的空间不会超过 $128MB$，运行所用的空间不会超过 $1.5s$，实际可用的空间至少为 $384MB$。

交互库正常运行需包含的头文件已经给出，你的程序可以包含你需要的头文件。

已经下发 green_sample.cpp，你可以在此基础上编写你的程序。

为符合评测的实际情况，本题实际评测使用的交互库与下发的交互库不完全相同。

本题的树不是动态变化的，即在询问开始前就是确定的，不会根据你的询问而变化。

你的程序不能进行任何读入、输出和文件操作。

通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为，所得分数无效。