p02976 AtCoder Grand Contest 035 - Even Degrees
You are given a simple connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects Vertex A_i and Vertex B_i. Takahashi will assign one of the two possible directions to each of the edges in the graph to make a directed graph. Determine if it is possible to make a directed graph with an even number of edges going out from every vertex. If the answer is yes, construct one such graph.

Constraints

* 2 \leq N \leq 10^5
* N-1 \leq M \leq 10^5
* 1 \leq A_i,B_i \leq N (1\leq i\leq M)
* The given graph is simple and connected.

Input

Input is given from Standard Input in the following format:


N M
A_1 B_1
:
A_M B_M


Output

If it is impossible to assign directions to satisfy the requirement, print -1. Otherwise, print an assignment of directions that satisfies the requirement, in the following format:


C_1 D_1
:
C_M D_M


Here each pair (C_i, D_i) means that there is an edge directed from Vertex C_i to Vertex D_i. The edges may be printed in any order.

Examples

Input

4 4
1 2
2 3
3 4
4 1


Output

1 2
1 4
3 2
3 4


Input

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


Output

-1
```python
n, m, *L = map(int, open(0).read().split())
con = [[] for _ in range(n)]
for s, t in zip(*[iter(L)] * 2):
	con[s - 1] += t - 1,
	con[t - 1] += s - 1,

# 辺を取り出して木をつくる
tree = [[] for _ in range(n)]
lev = [0] * n
vis = [False] * n
vis[0] = True
reserve = set()
q = [0]
while q:
	cur = q.pop()
	for nxt in con[cur]:
		if vis[nxt]:
			continue
		reserve.add((cur, nxt))
		tree[cur] += nxt,
		tree[nxt] += cur,
		lev[cur] += 1
		lev[nxt] += 1
		vis[nxt] = True
		q += nxt,

# 　要らない辺を適当に方向付ける
ans = []
deg = [0] * n
for s, t in zip(*[iter(L)] * 2):
	if (s - 1, t - 1) not in reserve and (t - 1, s - 1) not in reserve:
		ans += "{} {}".format(s, t),
		deg[s - 1] ^= 1

# 葉から順に辺の方向を決定
from collections import deque
q = deque()
done = [False] * n
for i, l in enumerate(lev):
	if l == 1:
		q.append(i)
while q:
	cur = q.popleft()
	for nxt in tree[cur]:
		if done[nxt]:
			continue
		if deg[cur]:
			ans += "{} {}".format(cur + 1, nxt + 1),
			deg[cur] ^= 1
		else:
			ans += "{} {}".format(nxt + 1, cur + 1),
			deg[nxt] ^= 1
		done[cur] = True
		lev[nxt] -= 1
		if lev[nxt] == 1:
			q.append(nxt)

if any(deg):
	print(-1)
else:
	print("\n".join(ans))

```