Deep Blue Tree

In a dream, in the hazy reflection of water, FanFan saw the deep blue tree that belonged only to him. When all dreams faded away, he forgot everything, except that the tree had \(n\) nodes. However, he clearly remembers \(m\) events. The \(i\)th event is described as: the unique simple path between node \(u_i\) and node \(v_i\) in the deep blue tree contains exactly \(2\) edges.

Your task is to help FanFan recall the appearance of this deep blue tree. If there are multiple valid trees, you only need to output any one of them.

Note that FanFan’s memories are fading too. Therefore, if you determine that no deep blue tree satisfying all \(m\) events exists, you must report that there is no solution by outputting -1.

A tree is an undirected connected graph with \(n-1\) edges and no cycles. For any two nodes in a tree, there exists a unique simple path between them.

Constraint from memories: For every given pair \((u,v)\), the distance between \(u\) and \(v\) in the tree must be exactly \(2\); that is, there must exist a node \(x\) (which is the unique common neighbor of \(u\) and \(v\)) such that the edges \((u,x)\) and \((x,v)\) are present, and \(u\) and \(v\) are not directly connected.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n \leq 10^5,\ 0 \leq m \leq 10^5)\), representing the number of nodes and the number of memories respectively. Each of the following \(m\) lines contains two integers \(u\) and \(v\) \((1 \leq u,v \leq n)\), indicating that in the deep blue tree the unique simple path between node \(u\) and node \(v\) must have exactly 2 edges.

You may assume that the input events are consistent with 1-indexed nodes.

outputFormat

If there exists a deep blue tree satisfying all \(m\) memories, output exactly \(n-1\) lines, each line containing two integers representing an edge of the tree. If multiple trees can satisfy the conditions, output any one of them.

If no such tree exists, output a single line with -1.

sample

4 1
2 3

1 2
1 3
1 4