题目背景

滥用本题评测者封号。

dottle bot。

题目描述

这是一道交互题，仅支持 C++ 提交。

有一棵未知的树，保证树的大小为奇数，你需要找到这棵树重心的编号。

你可以进行询问，每次询问你可以询问三个点 $(x,y,z)$，若不存在一条简单路径同时经过三个点，则交互器会返回 $0$，否则若存在，那么交互器会返回三个点在路径上相对顺序中间的一个点。

令 $dis(a,b)$ 表示 $a,b$ 两点在树上最短路径经过的边数，你也可以理解为:

若 $dis(x,y)+dis(x,z)=dis(y,z)$，则交互器会返回 $x$。

否则若 $dis(y,x)+dis(y,z)=dis(x,z)$，交互器会返回 $y$。

否则若 $dis(z,x)+dis(z,y)=dis(x,y)$，交互器会返回 $z$。

否则交互器会返回 $0$。

在最终的测试中，每个测试点会包含 $T$ 组测试数据，和一个常数 $M$，表示你在所有测试数据中询问次数总和的上限，具体细则见 输入格式 以及 数据范围。

实现细节

你需要引用 path.h 头文件。 本题中你只需要把 path.h 头文件的内容粘贴到程序开头即可，不要引用 path.h 头文件。

你需要实现下面的函数：

int centroid(int id,int N,int M);

其中 $id$ 为当前子任务的编号，$N$ 为当前询问树的大小，$M$ 为当前测试点剩余的询问次数，函数的返回值为当前树的重心编号。

具体的，在第一次调用时 $M$ 为当前测试点的询问次数上限，每次调用结束之后 $M$ 会减去当前测试点使用的询问次数。

你可以调用下面的函数：

int ask(int x,int y,int z);

表示你进行了一次询问，交互器会返回当前询问的答案，特别的，若询问次数已经超过了上限，交互器会返回 $-1$。

注意同一个测试点中 centroid 函数可能会被多次调用，请注意数组清空等情况。

下发文件中有样例交互库，该交互库的实现与评测时的交互库几乎一致，如果对交互方式有不理解可以参照交互库的代码理解。

输入格式

样例评测库将读入如下格式的输入数据：

第一行三个整数 $id,T,M$，表示当前的子任务编号以及测试数据的数量，以及询问次数的上界。

对于每一组测试数据，第一行一个正整数 $n$，表示当前测试数据中树的大小。

之后一行 $n-1$ 个正整数，第 $i$ 个数表示 $i+1$ 在以 $1$ 为根意义下的父亲节点。

数据的答案将在交互库内部计算。

输出格式

具体信息见交互库。

提示

数据范围

特殊性质 $A$：保证树的形态为一条链，即每个点的度数均不超过 $2$。

保证每个 Subtask 里的测试数据数量均不超过 $20$。请仔细阅读每一档子任务及其限制。

时空限制

Subtask 5 时限为 3s。

Subtask 7,8 时限为 4s。

其余 Subtask 时限为 1s。

空间限制：512MB。

保证最终交互库的时间使用不超过 2s，空间使用不超过 64MB。

下发文件

下发文件中有一个样例交互库，提供的交互头文件，一份示例代码，以及一个满足子任务 $4$ 性质的样例，选手也可以按照题目的输入格式构造其他样例。

另外也有一份洛谷样式的交互库。

保证下发的交互库和最终使用的交互库除反作弊之外没有区别，你可以使用这个交互库输出调试信息。