这是一道交互题。

网友小 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): 无特殊限制。