这是一道交互题。
网友小 Z 在纸上画了一棵包含了 $n$ 个点的树，点的编号为 $1 \sim n$。你并不知道这棵树的具体形态。
网友小 Z 想让你来猜猜这棵树的直径，你可以向她进行以下两种形式的提问：
- 给出三个两两不同的整数 $x,y,z$，网友小 Z 将会回答你 $dis(x,y)+dis(x,z)+dis(y,z)$ 的值。
- 给出三个整数 $x,y,z$，网友小 Z 将会回答你：$x$ 是否位于 $y$ 到 $z$ 的路径上。
其中 $dis(x,y)$ 表示 $x$ 到 $y$ 的路径上有多少条边。
对于每次猜测直径，你最多能提出 $3\times 10^5$ 次第一种类型的询问，$2$ 次第二种类型的询问。
在询问后，你需要告诉网友小 Z 这棵树的任意一条直径的两端。
在本题中，树的直径是树上最长的一条简单路径，直径可能有很多条，在本题中你只需要给出任意一条直径的路径两端。
实现细节
你不需要，也不应该实现主函数，你只需要实现下列函数：
std::pair<int, int> find_diameter(int task_id, int n)其中 $task\_id$ 表示子任务编号，$n$ 表示树的大小。 其返回值应为你找到的一条直径的两个端点。
你可以通过调用如下函数来向交互库发出询问：
int query(int x, int y, int z)你需要保证：
- $1 \leq x, y, z \leq n$
- $x \neq y, y \neq z, x \neq z$
调用此函数一次的时间复杂度为 $O(1)$，其返回值为 $dis(x,y)+dis(x,z)+dis(y,z)$。
bool in(int x, int y, int z)你需要保证：
- $1 \leq x, y, z \leq n$
调用此函数一次的时间复杂度为 $O(1)$，若 $x$ 位于 $y$ 到 $z$ 的路径上，其返回值为 $1$；否则，其返回值为 $0$。
在具体评测时，交互库可能会调用 find_diameter 多次，每次调用代表新的一轮猜直径游戏，树将会被重新设定。
本题保证所使用的树在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。
数据保证在第一种询问总次数不超过 $2 \times 10^7$ 且第二类询问总次数不超过 $20000$ 次的情况下，交互库运行所需的时间不超过 $3$ s；交互库使用的内存不超过 $256$ MB。
下发文件中包含我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。
你可以通过把下发的 grader.cpp 和 diameter.h，以及你自己想要提交的代码（比如该代码名为 diameter.cpp）放在同一文件目录下，然后使用如下命令编译得到可执行程序：g++ grader.cpp diameter.cpp -o diameter -O2 -lm
请确保你的程序开头有
#include "diameter.h"如果你是悲催的电脑盲，实在不会编译。没关系！你可以把 grader 的文件内容完整地粘贴到你的代码的 include 语句之后，然后直接编译你的代码就可以了！在提交前把 grader 的部分去掉即可。
以下是一份模板，你可以在此基础上修改得到你要提交的代码：
#include "diameter.h"
#include <bits/stdc++.h>
std::pair<int, int> find_diameter(int subid, int n) {
if (in(1, 2, 3))
return std::make_pair(1, 2);
if (query(1, 2, 3) == 233)
return std::make_pair(1, 3);
return std::make_pair(2, 3);
}输入
样例交互库从标准输入流读入以下数据：
第一行两个整数 $task_id,T$，分别表示子任务编号和数据组数。
对于一组数据，其输入格式为：
第一行一个整数 $n$ 表示树的大小。
接下来 $n-1$ 行，每行两个整数表示树的一条边。
输出
对于一组数据，若你的程序是正确的，交互库将输出 correct，否则会输出相应的错误信息。
若你的程序触发了不止一种错误，交互库只会输出其中一种。
样例数据
input
0 2 3 1 2 2 3 5 1 2 2 3 1 4 2 5
子任务
注意，尽管这些子任务 task_id 不同，但仍然配置了子任务依赖
对于全部的数据满足，$1\le T\le 10^4,1\le n\le 10^5,\sum n\le 10^6$。
Subtask 1(16pts): $T, n\le 100$。
Subtask 2(15pts): $n\le 10^4$。
Subtask 3(5pts): $n\le 2\times 10^4$。
Subtask 4(5pts): $n\le 3\times 10^4$。
Subtask 5(5pts): $n\le 4\times 10^4$。
Subtask 6(10pts): $n\le 5\times 10^4$。
Subtask 7(14pts): $n\le 6\times 10^4$。
Subtask 8(13pts): $n\le 7\times 10^4$。
Subtask 9(6pts): $n\le 8\times 10^4$。
Subtask 10(6pts): $n\le 9\times 10^4$。
Subtask 11(5pts): 无特殊限制。