I. The Hanged Man
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Claudette Morel is a botanist who is passionate about studying various plants. One day, while studying roses, she accidentally pricked her hand on a thorn. With her botany knowledge, she knew how to treat the wound, but more importantly, she wanted to prevent such incidents from happening again. To achieve this, she came up with a solution: make the rose thorns disappear.

The rose can be viewed as a tree with $$$n$$$ nodes. To make the rose thornless, Claudette Morel can add several edges to the graph, as long as the addition does not create multiple edges or self-loops. However, she cannot add new nodes to the graph.

A simple graph is thornless if and only if each edge appears in exactly one simple cycle. A simple cycle is defined as a cycle that does not contain any repeated nodes (except for the starting and ending node being the same). The following illustrations explain what is a thornless graph and what is not.

  • Left: This is a thornless graph.
  • Middle: This is not a thornless graph because the edge $$$(1,2)$$$ does not appear in any simple cycle.
  • Right: This is not a thornless graph because the edge $$$(1,2)$$$ appears in both cycles $$$1\sim 2\sim 5 \sim 4 \sim 1$$$ and $$$1\sim 2 \sim 5 \sim 3 \sim 1$$$.

Now, Claudette Morel has taken out her roses, and you are tasked with analyzing whether they can be transformed into a thornless graph.

Input

The input consists of multiple test cases. The first line contains a single integer $$$T$$$ ($$$1\le T\le 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of nodes in the tree.

Each of the following $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$), indicating that $$$(u_i,v_i)$$$ is an edge on the tree.

It is guaranteed that the sum of $$$n$$$ among $$$T$$$ test cases does not exceed $$$3\cdot 10^5$$$.

Output

For each test case, if the tree cannot be transformed into a thornless graph, output $$$-1$$$.

Otherwise, on the first line, output $$$k$$$ ($$$0 \le k \le n$$$) — the number of edges you added.

In the following $$$k$$$ lines, each line should contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$) — the edges you added. Note that after adding edges, multiple edges and self-loops are not allowed. If there are multiple solutions, print any.

Example

Input
3
4
1 2
2 3
2 4
7
1 2
1 3
1 4
4 5
4 6
4 7
6
1 2
2 3
2 4
1 5
5 6
Output
-1
3
1 5
2 3
6 7
2
6 2
4 3
Note
The left graph in the statement shows the second test case.