H. World Emperor
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed graph. For each vertex $$$v$$$, you can remove up to half of the edges directed away from $$$v$$$. Formally, if there are $$$x$$$ edges directed away from $$$v$$$, you can remove up to $$$\lfloor \frac{x}{2} \rfloor$$$ of them. Remove edges in such a way that vertex $$$n$$$ is not reachable from vertex $$$1$$$ or state that this is impossible.

For example, in the below graph, one solution is to remove the three red edges. Note that no vertex has more than half of the edges directed away from it colored red.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n \le 2\cdot 10^5, 0 \le m \le 2\cdot 10^5$$$) — the number of vertices and edges in the graph, respectively.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$), indicating that there is a directed edge from $$$u$$$ to $$$v$$$. All $$$(u, v)$$$ pairs are guaranteed to be distinct, but it is possible for there to be both an edge $$$(u, v)$$$ and an edge $$$(v, u)$$$.

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

Output

For each test case, if there is no solution, print $$$-1$$$.

Otherwise, the first line of output should contain a single integer $$$k$$$ ($$$0 \le k \le m$$$) — the number of edges to remove.

Each of the next $$$k$$$ lines should contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) — one of the edges $$$(u, v)$$$ that should be removed. $$$(u, v)$$$ must be present in the input graph, and no edge can be removed twice. Vertex $$$n$$$ should not be reachable from vertex $$$1$$$ after these removals.

If there are multiple solutions, print any.

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

The first test case corresponds to the image above. There are other solutions, such as choosing to only remove the edges $$$(1, 5)$$$ and $$$(4, 2)$$$.

In the second test case, the only valid solution is to remove only the edge $$$(2, 4)$$$.

This is the graph for the third test case. It can be shown there is no solution.