Cirno was recommended a game, and she decided to play it with Daiyousei today. Initially, there is a graph with 2 × n vertexes and m edges. At every turn, both Cirno and Daiyousei have to choose one distinct vertex. The degree of two choson vertexes must be the same. Then, Cirno and Daiyousei will remove them from the graph.
Now Cirno wanted to know is there any way to remove all the vertex from the given graph. If it exist, please give an example.
输入描述:
The fifirst line contains two integers, representing n and m.(1 ≤ n, m ≤ 106 )
For the following m lines, each line contains two integers u and v representing an edge.(1 ≤ u, v ≤ 2 × n)
It restricted that there are no multiple edges and self-loops.
输出描述:
If there is no way to remove all the vertexes from the given graph, output ">_<" (without quotation).
Otherwise, output n lines, each line contains two integers, representing vertexes chosen to remove in this
turn.
If there are many ways, output any of them.
示例2
输入
复制
5 12
7 5
1 7
10 4
6 7
3 4
5 4
10 8
9 1
3 7
6 10
2 4
2 8