E. Empty Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes.

Your task is to delete the entire tree with the following operation:

  • Choose any two connected nodes $$$x$$$ and $$$y$$$ $$$(1 \le x,y \le n$$$, $$$x \neq y)$$$ which have not been deleted. Then, delete all the nodes on the simple path between $$$x$$$ and $$$y$$$ (inclusive), and delete all the edges connected to these nodes.

If it is possible to delete the entire tree with operations, output any scheme. Otherwise, output $$$-1$$$ instead.

Input

The input consists of multiple test cases. The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$), the number of test cases.

The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 2000)$$$ — the number of vertices in the tree.

The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), indicating an edge between nodes $$$u$$$ and $$$v$$$.

It is guaranteed that the given input forms a tree.

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

Output

If it is possible to delete the entire tree with operations:

  • The first line of the output contains an integer $$$k$$$ $$$(1 \le k \le \lfloor \frac{n}{2} \lfloor)$$$  — the number of operations.
  • The $$$i$$$-th line contains $$$x_i$$$ and $$$y_i$$$ $$$(1 \leq x_i, y_i \leq n; x_i \neq y_i)$$$, where $$$x_i$$$ and $$$y_i$$$ denote the chosen nodes in the $$$i$$$-th operation.

Otherwise, output $$$-1$$$ instead.

Example
Input
4
3
1 2
2 3
4
1 2
2 3
2 4
5
1 2
1 3
2 4
2 5
7
1 2
1 3
1 4
4 5
5 6
5 7
Output
1
3 1
-1
2
4 5
1 3
-1
Note

In the second test case, no matter which $$$2$$$ nodes you choose at first, there will always be at least $$$1$$$ node that will be disconnected from the tree and can not be deleted any more.

In the third test case, select nodes $$$4$$$ and $$$5$$$ and delete every node in the simple path from $$$4$$$ to $$$5$$$, along with the edges connected to those nodes. Repeat the same process for nodes $$$1$$$ and $$$3$$$ (The nodes and edges to be deleted are marked in red).