G. Another Tree Query
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of $$$n$$$ nodes. Initially all node are disconnected. You have to process $$$m$$$ query. Queries are of two kind.

$$$1$$$ $$$u$$$ $$$v$$$ - add a bidirectional edge between node $$$u$$$ and $$$v$$$. It is guaranteed that, there is no path from $$$u$$$ to $$$v$$$ before this operation.

$$$2$$$ $$$u$$$ - Print two value $$$a$$$, $$$v$$$ . Where $$$a$$$ is maximum possible length of simple path starting from $$$u$$$. And $$$v$$$ is such a node so that $$$dist(u, v) = a$$$.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of each test cases follows.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ $$$(1 \le n \le 2 \cdot 10^5, n \le m \le 5 \cdot 10^5)$$$ — number of node in the final tree and number of query.

Each of the following $$$m$$$ lines contain three integers — a description of the next action in one of the following formats:

$$$1$$$ $$$u$$$ $$$v$$$ — $$$(1 \le u, v \le n, u \neq v)$$$.

$$$2$$$ $$$u$$$ — $$$(1 \le u \le n)$$$.

It is guaranteed that there will be $$$n - 1$$$ first type of query.

It is guaranteed that sum of $$$n$$$ over all test is $$$\le 2 \cdot 10^5 $$$ and sum of $$$m$$$ over all test case is $$$\le 5 \cdot 10^5$$$.

Output

For each query of type $$$2$$$ output the answer to it. If there are multiple answer, print any of them.

Example
Input
2
7 9
1 3 1
1 5 2
2 5
2 2
2 2
1 2 1
1 4 1
1 4 7
1 6 2
9 9
1 3 7
1 5 4
1 1 2
1 9 4
1 8 7
2 3
1 4 2
1 6 2
1 2 3
Output
1 2
1 5
1 5
2 8
Note

$$$dist(u, v)$$$ means number of edge in the simple path between $$$u$$$ and $$$v$$$.