I. Dependency Inversion
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Luisa Lopes is studying for her Software Engineering exam and has gotten stuck on the SOLID principles, which underpin the course.

To help the ideas sink in, she decides to examine the dependency graph of a legacy project she maintains as a freelancer. Each vertex represents a module, and a directed edge from $$$u$$$ to $$$v$$$ means that module $$$u$$$ depends directly on module $$$v$$$. A well-designed project should have no cyclic dependencies: no module should depend, directly or indirectly, on itself. Luisa suspects that her project has exactly this problem.

Thinking about the "D" in SOLID, the Dependency Inversion Principle, she starts wondering about reversing dependencies. Could reversing a single dependency eliminate all the cycles at once?

With little time left before her exam, Luisa asks for your help. Given a directed graph $$$G$$$, determine whether it can be made acyclic by reversing at most one edge. Reversing an edge $$$u \to v$$$ means replacing it with $$$v \to u$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \times 10^{5}$$$), the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \times 10^{5}$$$, $$$0 \leq m \leq \min(3 \times 10^{5},n(n-1)/2)$$$), the numbers of vertices and directed edges.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$, $$$u \neq v$$$), describing a directed edge from $$$u$$$ to $$$v$$$. For each unordered pair of vertices $$$\{u,v\}$$$, there is at most one edge between them.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^{5}$$$, and the sum of $$$m$$$ does not exceed $$$3 \times 10^{5}$$$.

Output

For each test case, print on the first line: 0 if the graph is already acyclic; 1 if it is not acyclic but reversing one edge can make it acyclic; or -1 otherwise.

If you print 1, print a second line containing two integers $$$u$$$ and $$$v$$$, identifying an edge $$$u \to v$$$ whose reversal makes the graph acyclic. Any such edge is accepted. Print its endpoints in their original input order.

Examples
Input
1
4 4
1 2
2 3
3 1
3 4
Output
1
1 2
Input
1
6 6
1 2
2 3
3 1
4 5
5 6
6 4
Output
-1
Input
4
2 1
1 2
1 0
3 3
1 2
2 3
3 1
6 6
1 2
2 3
3 1
4 5
5 6
6 4
Output
0
0
1
1 2
-1
Note

Explanation for example 1

In the first example, reversing edge $$$1 \to 2$$$ breaks the only cycle, so printing 1 followed by 1 2 is accepted. Any other edge whose reversal makes the graph acyclic would also be accepted.

Explanation for example 2

Here, the graph is not acyclic, and reversing one edge cannot make it acyclic. The expected output is therefore -1.