D. Connecting the Conflicts
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A tree is a connected graph without cycles. Define an independent set of a tree as a set of vertices such that no two distinct vertices in the set are directly connected by an edge in the tree. A maximum independent set is an independent set that contains the largest possible number of vertices.

Given a forest of $$$k$$$ trees, we want to add $$$k-1$$$ edges to unite the forest into a single tree so as to maximize the size of the maximum independent set of the resulting tree. Please find the additional edges.

If there are several valid answers, you may output any of them.

Input

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

The first line of each test case contains a single integer $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) — the number of trees in the forest.

This is followed by a description of each of the $$$k$$$ trees, which are numbered $$$1, 2, \ldots, k$$$ in order:

The first line contains a single integer $$$n$$$ ($$$1\le n \le 2 \cdot 10^5$$$) — the size of the tree. The vertices of the tree are numbered with integers from $$$1$$$ to $$$n$$$.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$k-1$$$ lines; each line contains four integers $$$t_1, v_1, t_2, v_2$$$, denoting an edge between $$$(t_1,v_1)$$$ and $$$(t_2,v_2)$$$ that is added to the original graph.

Note that we number all $$$k$$$ trees from $$$1$$$ to $$$k$$$ in the order in which they appear in the input data. For any tree $$$i$$$ ($$$1\le i \le k$$$), if it contains $$$n$$$ nodes, then its nodes are numbered from $$$1$$$ to $$$n$$$. The $$$j$$$-th node in this tree is denoted by $$$(i,j)$$$.

Example
Input
2
2
1
1
2
3
1 2
1 3
1
Output
2 1 1 1
2 1 1 1
Note

In the first test case, the graph has two vertices and no edge; adding an edge between these two nodes is the only way to turn the graph into a tree.

In the second test case, we can add an edge between the only vertex $$$1$$$ of tree $$$2$$$ and one of the vertices $$$1$$$, $$$2$$$, and $$$3$$$ of tree $$$1$$$.

  • add edge $$$(2,1)-(1,1)$$$, the size of a maximum independent set of the resulting tree is 3.
  • add edge $$$(2,1)-(1,2)$$$, the size of a maximum independent set of the resulting tree is 2.
  • add edge $$$(2,1)-(1,3)$$$, the size of a maximum independent set of the resulting tree is 2.

So, we choose the edge $$$(2,1)-(1,1)$$$ since it is optimal.