This is an interactive problem.

User Xiao Z has drawn a tree with $n$ nodes on a piece of paper, with nodes labeled $1 \sim n$. You do not know the specific structure of this tree.

Xiao Z wants you to guess the diameter of this tree. You can ask her the following two types of questions:

• Given three distinct integers $x, y, z$, Xiao Z will return the value of $dis(x, y) + dis(x, z) + dis(y, z)$.
• Given three integers $x, y, z$, Xiao Z will return whether $x$ lies on the path between $y$ and $z$.

Here, $dis(x, y)$ denotes the number of edges on the path between $x$ and $y$.

For each diameter guess, you can ask at most $3 \times 10^5$ questions of the first type and $2$ questions of the second type.

After asking your questions, you need to tell Xiao Z the two endpoints of any diameter of the tree.

In this problem, the diameter of a tree is the longest simple path in the tree. There may be many diameters; you only need to provide the two endpoints of any one of them.

Implementation Details

You do not need to, and should not, implement the main function. You only need to implement the following function:

std::pair<int, int> find_diameter(int task_id, int n)

Here, task_id represents the subtask ID, and n represents the size of the tree. The return value should be the two endpoints of a diameter you found.

You can call the following functions to send queries to the interactor:

int query(int x, int y, int z)

You must ensure:

• $1 \leq x, y, z \leq n$
• $x \neq y, y \neq z, x \neq z$

The time complexity of calling this function once is $O(1)$, and its return value is $dis(x, y) + dis(x, z) + dis(y, z)$.

bool in(int x, int y, int z)

You must ensure:

• $1 \leq x, y, z \leq n$

The time complexity of calling this function once is $O(1)$. If $x$ lies on the path between $y$ and $z$, it returns $1$; otherwise, it returns $0$.

During evaluation, the interactor may call find_diameter multiple times. Each call represents a new round of the diameter-guessing game, and the tree will be reset.

This problem guarantees that the tree used is fully determined before the interaction begins and is not constructed dynamically based on your program's interaction. Therefore, the interaction operations are deterministic, and you do not need to worry about the specific implementation of these operations within the interactor.

It is guaranteed that if the total number of first-type queries does not exceed $2 \times 10^7$ and the total number of second-type queries does not exceed $20000$, the interactor will run within $3$ seconds and use no more than $256$ MB of memory.

The provided files include a reference implementation of the interactor. The interactor used during final testing may differ from this reference, so your solution should not rely on the specific implementation of the interactor.

You can place the provided grader.cpp and diameter.h, along with your code (e.g., named diameter.cpp), in the same directory and compile them using the following command: g++ grader.cpp diameter.cpp -o diameter -O2 -lm

Please ensure your program starts with:

#include "diameter.h"

If you are not familiar with compilation, you can simply paste the entire content of the grader into your code after the include statement and compile it directly. Remember to remove the grader part before submitting.

Below is a template you can modify to create your submission:

#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);
}

Input

The sample interactor reads the following data from standard input:

The first line contains two integers $task\_id$ and $T$, representing the subtask ID and the number of test cases, respectively.

For each test case, the input format is:

The first line contains an integer $n$, the size of the tree.

The next $n-1$ lines each contain two integers representing an edge of the tree.

Output

For each test case, if your program is correct, the interactor will output correct; otherwise, it will output the corresponding error message.

If your program triggers more than one type of error, the interactor will only output one of them.

Examples

Input 1

0 2
3
1 2
2 3
5
1 2
2 3
1 4
2 5

Output 1

correct
correct

Subtasks

Note: Although these subtasks have different task_id values, they still have subtask dependencies.

For all data, $1 \le T \le 10^4, 1 \le n \le 10^5, \sum n \le 10^6$.

Subtask 1 (16 pts): $T, n \le 100$.

Subtask 2 (15 pts): $n \le 10^4$.

Subtask 3 (5 pts): $n \le 2 \times 10^4$.

Subtask 4 (5 pts): $n \le 3 \times 10^4$.

Subtask 5 (5 pts): $n \le 4 \times 10^4$.

Subtask 6 (10 pts): $n \le 5 \times 10^4$.

Subtask 7 (14 pts): $n \le 6 \times 10^4$.

Subtask 8 (13 pts): $n \le 7 \times 10^4$.

Subtask 9 (6 pts): $n \le 8 \times 10^4$.

Subtask 10 (6 pts): $n \le 9 \times 10^4$.

Subtask 11 (5 pts): No special restrictions.