A. Two's Company but Three's Trumpery
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Let's review some knowledge of graph theory. In this problem, all the graphs discussed are undirected graphs.

  • Connected graph: A graph is said to be connected if there exists a path between every pair of different nodes.
  • Bridge: A bridge is an edge of a connected graph whose deletion makes the graph not connected.
  • 2-edge-connected: A 2-edge-connected graph is a connected graph that does not have any bridges.
  • 3-cycle: Nodes $$$(u,v,w)$$$ are said to be a 3-cycle if $$$(u,v)$$$, $$$(v,w)$$$, and $$$(u,w)$$$ are all directly connected by an edge.

Now given an undirected acyclic graph with $$$n$$$ nodes and $$$m$$$ edges (i.e., a forest), you need to add some edges to make the graph 2-edge-connected and have no 3-cycle. Please output the minimum number of edges to add and how to add them.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), indicating the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5,0\le m\le n-1$$$), indicating the number of nodes and edges in the graph.

Each of the following $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), indicating an undirected edge connecting $$$u$$$ and $$$v$$$. It's guaranteed that there are no self-loops or multiple edges in the graph. It's also guaranteed that any two vertices in the graph are connected by at most one path.

It's guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$10^5$$$.

Output

For each test case, output an integer $$$k$$$ in the first line indicating the minimum number of edges to add. Then each of the following $$$k$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), indicating an undirected edge connecting $$$u$$$ and $$$v$$$. You need to ensure that there are no self-loops or multiple edges in the graph after adding edges.

If there are multiple solutions with the minimum $$$k$$$, output any. If there are no possible solutions, output $$$-1$$$ in a single line.

Example
Input
3
5 0
5 4
1 2
1 3
2 4
2 5
5 4
1 2
1 3
1 4
1 5
Output
5
1 2
1 3
2 4
3 5
5 4
2
3 4
3 5
-1