Problem Statement

There is a directed graph with $N$ vertices and $M$ edges. This graph is not necessarily a simple graph, but it has no self-loops. The vertices are numbered from $1$ to $N$. The $i$-th edge goes out of vertex $U_i$ and points to vertex $V_i$. For each vertex $x$, let $p_x$ be the number of edges going out of vertex $x$, let $n_x$ be the number of edges pointing to vertex $x$, and define $d_x=p_x-n_x$.

You create a new graph by choosing $0$ or more edges of this graph and removing them. Determine whether there exists a possible new graph that satisfies all of the following conditions, and if one exists, find $1$ such graph.

• For each vertex $x$, the value of $d_x$ has not changed compared with the original graph.
• It has no cycles.

Output the graph you found in the same format as the input.

Constraints

The input satisfies the following constraints.

• $1 \leq N \leq 300\, 000$
• $0 \leq M \leq 300\, 000$
• $1 \leq U_i , V_i \leq N$
• $U_i \neq V_i$
• All values are integers.

Input

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

Output

If no new graph satisfying the conditions exists, output only $1$ line containing -1.

If one exists, output that graph in the same format as the input. If there are multiple graphs satisfying the conditions in the problem statement, you may output any of them. The edges may be in any order. Just in case, end the output with a newline.

Sample

5 7
1 2
1 3
1 5
2 4
3 4
4 1
5 2

5 4
1 2
1 5
2 4
5 2

5 3
1 3
3 4
1 2

10 20
7 5
3 2
5 2
2 1
3 5
10 3
6 7
8 6
5 3
7 3
5 1
8 7
2 3
2 6
2 4
10 5
1 8
2 4
10 9
10 2

10 10
5 2
2 1
10 3
8 6
2 3
2 4
10 5
2 4
10 9
10 2