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

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(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))


import os
import sys
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(N, M) = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
graph = [[] for _ in range(N + 1)]
for (a, b) in AB:
	graph[a].append(b)
	graph[b].append(a)

def spanning_tree(root, ret=None, seen=None):
	if ret is None:
		ret = [set() for _ in range(N + 1)]
	if seen is None:
		seen = [False] * (N + 1)
		seen[root] = True
	for v in graph[root]:
		if seen[v]:
			continue
		ret[root].add(v)
		seen[v] = True
		ret = spanning_tree(v, ret, seen)
	return ret
if M % 2 == 1:
	print(-1)
	exit()
root = 1
st = spanning_tree(root)
outdeg = [0] * (N + 1)
ans = []
for (a, b) in AB:
	if a not in st[b] and b not in st[a]:
		ans.append((a, b))
		outdeg[a] += 1

def dfs(par):
	for v in st[par]:
		if st[v]:
			dfs(v)
		if outdeg[v] % 2 == 0:
			ans.append((par, v))
			outdeg[par] += 1
		else:
			ans.append((v, par))
			outdeg[v] += 1
dfs(root)
for r in ans:
	print(*r)


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)
(N, M) = [int(i) for i in input().split()]
if M % 2 == 1:
	print(-1)
	exit()
E = [[] for i in range(N + 1)]
used_e = [False] * M
ans = []
for i in range(M):
	(A, B) = map(int, input().split())
	E[A].append((B, i))
	E[B].append((A, i))
visited = [False] * (N + 1)

def dfs(prev, v):
	if visited[v]:
		return
	visited[v] = True
	cnt = 0
	for (to, i) in E[v]:
		dfs(v, to)
		if not used_e[i]:
			cnt += 1
	for (to, i) in E[v]:
		if cnt % 2 == 1 and to == prev:
			continue
		if not used_e[i]:
			ans.append((v, to))
			used_e[i] = True
dfs(0, 1)
for a in ans:
	print(*a)


import sys
input = sys.stdin.readline
from collections import deque
(n, m) = map(int, input().split())
Edges = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	Edges[a].append(b)
	Edges[b].append(a)
if m % 2:
	print(-1)
	exit()
Ans = []
AnsSet = set()
Par = [-1] * n
V = []
Visited = [False] * n
Cnt = [0] * n
q = deque([0])
Visited[0] = True
while q:
	fr = q.popleft()
	for to in Edges[fr]:
		if to == Par[fr] or (to, fr) in AnsSet:
			continue
		if Visited[to]:
			AnsSet.add((fr, to))
			Ans.append((fr, to))
			Cnt[fr] += 1
		else:
			Par[to] = fr
			Visited[to] = True
			q.append(to)
			V.append(to)
for v in V[::-1]:
	if Cnt[v] % 2:
		Ans.append((v, Par[v]))
	else:
		Ans.append((Par[v], v))
		Cnt[Par[v]] += 1
for (c, d) in Ans:
	print(c + 1, d + 1)


(n, m) = map(int, input().split())
es = [None] * n
for i in range(n):
	es[i] = []
for (a, b) in (map(lambda x: int(x) - 1, input().split()) for _ in range(m)):
	es[a].append(b)
	es[b].append(a)
if m % 2:
	print(-1)
	quit(0)
mst_es = [None] * n
for i in range(n):
	mst_es[i] = set()
st = []
used = [False] * n
st.append(0)
used[0] = True
degrees = [0] * n
num_edges = [0] * n
while st != []:
	v = st.pop()
	for u in es[v]:
		if used[u]:
			if v not in mst_es[u] and u < v:
				print(u + 1, v + 1)
				degrees[u] += 1
		else:
			num_edges[u] += 1
			num_edges[v] += 1
			used[u] = True
			(a, b) = (u, v) if u < v else (v, u)
			st.append(u)
			mst_es[a].add(b)
			mst_es[b].add(a)
st = [v for v in range(n) if num_edges[v] == 1]
while st != []:
	v = st.pop()
	if num_edges[v] < 1:
		continue
	for u in mst_es[v]:
		(a, b) = (v, u) if degrees[v] % 2 == 1 else (u, v)
		print(a + 1, b + 1)
		degrees[a] += 1
	num_edges[u] -= 1
	num_edges[v] -= 1
	mst_es[v].remove(u)
	mst_es[u].remove(v)
	if num_edges[u] == 1:
		st.append(u)


import sys
sys.setrecursionlimit(1000000)
(N, M) = map(int, input().split())
if M % 2 == 1:
	print(-1)
	exit()
E = []
A = [[] for _ in range(N)]
for _ in range(M):
	(i, j) = map(int, input().split())
	E.append([i - 1, j - 1])
	A[i - 1].append(j - 1)
	A[j - 1].append(i - 1)
tree = [[] for _ in range(N)]
visited = [False] * N
queue = [0]
visited[0] = True
while queue:
	i = queue.pop()
	for j in A[i]:
		if not visited[j]:
			tree[i].append(j)
			tree[j].append(i)
			visited[j] = True
			queue.append(j)
D = [0] * N
for (i, j) in E:
	if i not in tree[j]:
		print(i + 1, j + 1)
		D[i] += 1

def f(parent, i):
	for j in tree[i]:
		if j == parent:
			continue
		f(i, j)
		if D[j] % 2 == 0:
			print(i + 1, j + 1)
			D[i] += 1
		else:
			print(j + 1, i + 1)
			D[j] += 1
	return
f(0, 0)


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)
(n, m) = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for i in range(m)]
if m % 2 == 1:
	print(-1)
	exit()
E = [[] for i in range(n + 1)]
used_e = [False] * m
ans = []
for (i, (a, b)) in enumerate(A):
	E[a].append((b, i))
	E[b].append((a, i))
used = [False] * (n + 1)

def dfs(prev, v):
	if used[v]:
		return
	used[v] = True
	cnt = 0
	for (to, i) in E[v]:
		dfs(v, to)
		if not used_e[i]:
			cnt += 1
	for (to, i) in E[v]:
		if cnt % 2 == 1 and to == prev:
			continue
		if not used_e[i]:
			ans.append((v, to))
			used_e[i] = True
dfs(0, 1)
for a in ans:
	print(*a)


from collections import deque
(N, M) = map(int, input().split())
V = {i: [] for i in range(1, N + 1)}
for _ in range(M):
	(a, b) = map(int, input().split())
	V[a].append(b)
	V[b].append(a)

def zen(V):
	W = []
	q = deque()
	q.append(1)
	vstd = {i: 0 for i in range(1, N + 1)}
	while q:
		u = q.popleft()
		if vstd[u]:
			continue
		vstd[u] = True
		W.append(u)
		for v in V[u]:
			if vstd[v]:
				continue
			q.append(v)
	return W
if M % 2 != 0:
	print(-1)
else:
	U = zen(V)
	W = {i: [] for i in range(1, N + 1)}
	for u in U[::-1]:
		for v in V[u]:
			if v in W[u] or u in W[v]:
				continue
			if len(W[u]) % 2 == 0:
				W[v].append(u)
			else:
				W[u].append(v)
	for w in W:
		for v in W[w]:
			print(w, v)


from collections import deque

class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n
		self.cnt = n

	def root(self, x):
		if self.parent[x] < 0:
			return x
		else:
			self.parent[x] = self.root(self.parent[x])
			return self.parent[x]

	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x != y:
			if self.parent[x] > self.parent[y]:
				(x, y) = (y, x)
			self.parent[x] += self.parent[y]
			self.parent[y] = x
			self.cnt -= 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def get_size(self, x):
		return -self.parent[self.root(x)]

	def get_cnt(self):
		return self.cnt
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
if m % 2 != 0:
	print(-1)
	exit()
uf = UnionFind(n)
tree = [[] for i in range(n)]
cnt = [0] * n
ans = []
for i in range(m):
	(a, b) = info[i]
	a -= 1
	b -= 1
	if uf.is_same(a, b):
		cnt[a] += 1
		ans.append((a + 1, b + 1))
	else:
		uf.merge(a, b)
		tree[a].append(b)
		tree[b].append(a)
root = 0
tps = [None] * n
q = deque([(-1, root)])
i = 0
while q:
	(par, pos) = q.pop()
	tps[i] = (par, pos)
	i += 1
	for child in tree[pos]:
		if par == child:
			continue
		else:
			q.append((pos, child))
for (par, pos) in tps[::-1]:
	if par == -1:
		continue
	if cnt[pos] % 2 == 0:
		cnt[par] += 1
		ans.append((par + 1, pos + 1))
	else:
		cnt[pos] += 1
		ans.append((pos + 1, par + 1))
for i in ans:
	print(*i)


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
(n, m) = [int(item) for item in input().split()]
if m % 2 != 0:
	print(-1)
	exit()
visited_e = [False] * m
visited_v = [False] * n
edge = [[] for _ in range(n)]
for i in range(m):
	(a, b) = [int(item) for item in input().split()]
	a -= 1
	b -= 1
	edge[a].append([b, i])
	edge[b].append([a, i])
ans = []

def dfs(prev, n):
	if visited_v[n]:
		return 1
	visited_v[n] = True
	child_num = 0
	for (v, index) in edge[n]:
		if visited_e[index]:
			continue
		visited_e[index] = True
		if dfs(n, v) == 1:
			child_num += 1
			ans.append([n + 1, v + 1])
	if child_num % 2 == 0:
		return 1
	else:
		ans.append([n + 1, prev + 1])
		return 0
dfs(-1, 0)
print('\n'.join([str(f) + ' ' + str(t) for (f, t) in ans]))


def b_even_degrees(N, M, Edges):
	if M % 2 == 1:
		return -1
	import sys
	sys.setrecursionlimit(10 ** 6)
	graph = [[] for _ in range(N + 1)]
	for (a, b) in Edges:
		graph[a].append(b)
		graph[b].append(a)

	def make_spanning_tree(current, ret=None, is_visit=None):
		if ret is None:
			ret = [set() for _ in range(N + 1)]
		if is_visit is None:
			is_visit = [False] * (N + 1)
			is_visit[current] = True
		for next_vertex in graph[current]:
			if is_visit[next_vertex]:
				continue
			ret[current].add(next_vertex)
			is_visit[next_vertex] = True
			ret = make_spanning_tree(next_vertex, ret, is_visit)
		return ret
	root_vertex = 1
	spanning_tree = make_spanning_tree(root_vertex)
	outdegree = [0] * (N + 1)
	ans = []
	for (a, b) in Edges:
		if a not in spanning_tree[b] and b not in spanning_tree[a]:
			ans.append((a, b))
			outdegree[a] += 1

	def dfs(current):
		for child in spanning_tree[current]:
			if spanning_tree[child]:
				dfs(child)
			if outdegree[child] % 2 == 0:
				ans.append((current, child))
				outdegree[current] += 1
			else:
				ans.append((child, current))
				outdegree[child] += 1
	dfs(root_vertex)
	ans.sort()
	return '\n'.join((' '.join(map(str, row)) for row in ans))
(N, M) = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(b_even_degrees(N, M, Edges))


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from collections import deque
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	adj = [[] for _ in range(N + 1)]
	if M & 1:
		print(-1)
		exit()
	ans = []
	E2i = {}
	num = [0] * (N + 1)
	for i in range(M):
		(a, b) = map(int, input().split())
		adj[a].append(b)
		adj[b].append(a)
		ans.append((a, b))
		E2i[a * (N + 1) + b] = i
		E2i[b * (N + 1) + a] = i
		num[a] += 1
	que = deque()
	que.append(1)
	seen = [-1] * (N + 1)
	seen[1] = 0
	par = [0] * (N + 1)
	child = [[] for _ in range(N + 1)]
	seq = []
	while que:
		v = que.popleft()
		seq.append(v)
		for u in adj[v]:
			if seen[u] == -1:
				seen[u] = seen[v] + 1
				par[u] = v
				child[v].append(u)
				que.append(u)
	seq.reverse()
	for v in seq:
		if v == 1:
			continue
		if num[v] & 1:
			p = par[v]
			i = E2i[v * (N + 1) + p]
			if ans[i] == (p, v):
				ans[i] = (v, p)
				num[v] += 1
				num[p] -= 1
			else:
				ans[i] = (p, v)
				num[p] += 1
				num[v] -= 1
	for (c, d) in ans:
		print(c, d)
main()


class Bridge:

	def __init__(self, nodeA, nodeB):
		self.edges = [Edge(nodeA, self), Edge(nodeB, self)]
		nodeA.addEdge(self.edges[1])
		nodeB.addEdge(self.edges[0])
		self.dir = True
		self.vec = None

	def __repr__(self):
		return str((self.vec, self.dir))

class Edge:

	def __init__(self, node, bridge):
		self.bridge = bridge
		self.node = node

	def another(self):
		return self.bridge.edges[1 if self.bridge.edges[0] == self else 0]

class Node:

	def __init__(self, id):
		self.id = id
		self.edges = []
		self.parent = None
		self.judge = True

	def addEdge(self, edge):
		self.edges.append(edge)

	def __repr__(self):
		return str((self.id, None if self.parent is None else self.parent.node.id, self.judge))
(N, M) = map(int, input().split())
nodes = [Node(i) for i in range(N + 1)]
bridges = []
for (A, B) in (map(int, input().split()) for _ in range(M)):
	bridges.append(Bridge(nodes[A], nodes[B]))
s = [nodes[1]]
idx = 0
while len(s) > 0:
	cur = s.pop()
	isleaf = True
	for nxt in cur.edges:
		if nxt.bridge.vec is None:
			cur.judge ^= True
			nxt.bridge.vec = (cur.id, nxt.node.id)
			if nxt.node.parent is None:
				isleaf = False
				nxt.node.parent = nxt.another()
				s.append(nxt.node)
	if isleaf:
		if len(s) > 0 and s[-1].parent is not None:
			nl = s[-1].parent.node
		else:
			nl = nodes[1]
		while cur.parent is not None and cur != nl:
			if not cur.judge:
				cur.judge ^= True
				cur.parent.node.judge ^= True
				cur.parent.bridge.dir ^= True
			cur = cur.parent.node
if nodes[1].judge:
	for br in bridges:
		if br.dir:
			print('{} {}'.format(br.vec[0], br.vec[1]))
		else:
			print('{} {}'.format(br.vec[1], br.vec[0]))
else:
	print('-1')


from collections import defaultdict
from copy import deepcopy
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
if m % 2 == 1:
	print(-1)
	exit()
graph = defaultdict(set)
grapht = defaultdict(set)
for i in range(m):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	graph[a].add(b)
	graph[b].add(a)
	grapht[a].add(b)
	grapht[b].add(a)
graph2 = defaultdict(set)
visited = [0 for i in range(n)]
num = [1 for i in range(n)]

def dfs(x):
	visited[x] = 1
	for nx in graph[x]:
		if not visited[nx]:
			dfs(nx)
	t = set()
	if num[x] == 1 and len(grapht[x]) % 2 == 0:
		for e in grapht[x]:
			graph2[x].add(e)
			t.add(e)
	elif num[x] == -1 and len(grapht[x]) % 2 == 0:
		for (j, e) in enumerate(grapht[x]):
			if j == len(grapht[x]) - 1:
				graph2[e].add(x)
				num[e] *= -1
			else:
				graph2[x].add(e)
			t.add(e)
	elif num[x] == 1 and len(grapht[x]) % 2 == 1:
		for (j, e) in enumerate(grapht[x]):
			if j == len(grapht[x]) - 1:
				graph2[e].add(x)
				num[e] *= -1
			else:
				graph2[x].add(e)
			t.add(e)
	elif num[x] == -1 and len(grapht[x]) % 2 == 1:
		for e in grapht[x]:
			graph2[x].add(e)
			t.add(e)
	for e in t:
		grapht[x].remove(e)
		grapht[e].remove(x)
dfs(0)
for i in range(n):
	if len(graph2[i]) % 2 == 1:
		print(-1)
		exit()
for i in range(n):
	for e in graph2[i]:
		print(i + 1, e + 1)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop, heappush
from collections import defaultdict
(n, m) = map(int, readline().split())
ab = list(map(int, read().split()))
if m % 2 == 1:
	print(-1)
	exit()
it = iter(ab)
links = [[] for _ in range(n + 1)]
for (a, b) in zip(it, it):
	links[a].append(b)
	links[b].append(a)
depth = [-1] * (n + 1)
parent = [0] * (n + 1)
child = [set() for _ in range(n + 1)]
hq_dep = []
stack = [1]
depth[1] = 0
now_dep = 1
while stack:
	stack2 = []
	while stack:
		i = stack.pop()
		for j in links[i]:
			if depth[j] == -1:
				depth[j] = now_dep
				parent[j] = i
				heappush(hq_dep, (now_dep * -1, j))
				stack2.append(j)
			else:
				child[j].add(i)
	now_dep += 1
	stack = stack2[:]
ans = []
d = defaultdict(int)
outs = [0] * (n + 1)
while hq_dep:
	(i_dep, i) = heappop(hq_dep)
	for j in child[i]:
		if d[min(i, j) * 10 ** 6 + max(i, j)] == 0:
			d[min(i, j) * 10 ** 6 + max(i, j)] = 1
			outs[j] += 1
			ans.append([j, i])
	j = parent[i]
	if outs[i] % 2 == 1:
		d[min(i, j) * 10 ** 6 + max(i, j)] = 1
		outs[i] += 1
		ans.append([i, j])
	else:
		d[min(i, j) * 10 ** 6 + max(i, j)] = 1
		outs[j] += 1
		ans.append([j, i])
print('\n'.join(map(lambda x: ' '.join(map(str, x)), ans)))


(N, M) = map(int, input().split())
if M % 2 != 0:
	print(-1)
	exit()
graph = [[] for _ in range(N)]
for _ in range(M):
	(u, v) = map(int, input().split())
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
ans = []
parent = [-1] * N
visited = [False] * N
ctr = [0] * N
record = []
que = [(-1, 0)]
while que:
	(pre, u) = que.pop()
	if visited[u]:
		ctr[u] += 1
		if pre >= 0:
			ans.append((u, pre))
		continue
	visited[u] = True
	record.append(u)
	for v in graph[u]:
		if v != parent[u]:
			parent[v] = u
			graph[v].remove(u)
			que.append((u, v))
for u in record[1:][::-1]:
	if ctr[u] % 2 == 1:
		ans.append((u, parent[u]))
	else:
		ans.append((parent[u], u))
		ctr[parent[u]] += 1
for (x, y) in ans:
	print(x + 1, y + 1)


from collections import deque
(N, M) = map(int, input().split())
G = dict()
edge_dict = dict()
count_list = [0] * (N + 1)
for i in range(1, N + 1):
	G[i] = dict()
	edge_dict[i] = dict()
for _ in range(M):
	(A, B) = map(int, input().split())
	if A > B:
		(A, B) = (B, A)
	G[A][B] = 1
	G[B][A] = 1
	edge_dict[A][B] = 1
	edge_dict[B][A] = -1
	count_list[A] += 1
if M % 2 == 1:
	print(-1)
else:
	parent = [0] * (N + 1)
	node_list = []
	queue = deque([1])
	visited = [0] * (N + 1)
	while len(queue) > 0:
		p = queue.popleft()
		for q in G[p].keys():
			if visited[q]:
				continue
			else:
				parent[q] = p
				visited[q] = 1
				queue.append(q)
				node_list.append(q)
	while len(node_list) > 0:
		q = node_list.pop()
		p = parent[q]
		if count_list[q] % 2 == 1:
			edge_dict[p][q] *= -1
			edge_dict[q][p] *= -1
			count_list[p] += 1
			count_list[q] += 1
	for i in range(1, N + 1):
		for j in edge_dict[i].keys():
			if edge_dict[i][j] == 1:
				print(i, j)


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(M)]
if M % 2:
	print(-1)
	exit()

class UnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.rank = [0] * N
		self.count = 0

	def root(self, a):
		if self.parent[a] == a:
			return a
		else:
			self.parent[a] = self.root(self.parent[a])
			return self.parent[a]

	def is_same(self, a, b):
		return self.root(a) == self.root(b)

	def unite(self, a, b):
		ra = self.root(a)
		rb = self.root(b)
		if ra == rb:
			return
		if self.rank[ra] < self.rank[rb]:
			self.parent[ra] = rb
		else:
			self.parent[rb] = ra
			if self.rank[ra] == self.rank[rb]:
				self.rank[ra] += 1
		self.count += 1
uf = UnionFind(N)
outdeg = [0] * N
es = [[] for _ in range(N)]
ans = []
for (a, b) in AB:
	(a, b) = (a - 1, b - 1)
	if uf.is_same(a, b):
		outdeg[a] += 1
		ans.append((a + 1, b + 1))
	else:
		uf.unite(a, b)
		es[a].append(b)
		es[b].append(a)

def rec(v, p=-1):
	k = outdeg[v]
	for to in es[v]:
		if to == p:
			continue
		r = rec(to, v)
		if r:
			ans.append((to + 1, v + 1))
		else:
			ans.append((v + 1, to + 1))
		k += r + 1
	return k % 2
rec(0)
for row in ans:
	print(*row)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import deque
(n, m) = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(m)]
repn = [[] for j in range(n)]
for (a, b) in AB:
	a -= 1
	b -= 1
	repn[a].append(b)
	repn[b].append(a)
tree = [set() for i in range(n)]
visited = [False] * n
visited[0] = True
q = deque([0])
while q:
	u = q.popleft()
	for v in repn[u]:
		if visited[v]:
			continue
		visited[v] = True
		tree[u].add(v)
		tree[v].add(u)
		q.append(v)
degree = [0] * n
ans = []
for (a, b) in AB:
	a -= 1
	b -= 1
	if b in tree[a]:
		continue
	ans.append('{} {}'.format(a + 1, b + 1))
	degree[a] += 1

def dfs(u=0, parent=None):
	for v in tree[u]:
		if v == parent:
			continue
		dfs(v, u)
		if degree[v] % 2 == 0:
			ans.append('{} {}'.format(u + 1, v + 1))
			degree[u] += 1
		else:
			ans.append('{} {}'.format(v + 1, u + 1))
			degree[v] += 1
dfs()
if degree[0] % 2 == 1:
	print(-1)
else:
	print('\n'.join(ans))


from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(i, oi=-1, d=0):
	dep[d] += [i]
	oya[i] = oi
	for ki in to[i]:
		if ki == oi:
			continue
		if oya[ki] > -2:
			if i < ki:
				print(i + 1, ki + 1)
				ne[i] += 1
			continue
		dfs(ki, i, d + 1)
to = defaultdict(list)
dep = defaultdict(list)
(n, m) = map(int, input().split())
if m % 2:
	print(-1)
	exit()
oya = [-2] * n
ne = [0] * n
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	to[a] += [b]
	to[b] += [a]
dfs(0)
for (k, v) in sorted(dep.items(), reverse=True):
	for i in v:
		if ne[i] % 2:
			print(i + 1, oya[i] + 1)
		else:
			print(oya[i] + 1, i + 1)
			ne[oya[i]] += 1
	if k == 1:
		break


import sys
sys.setrecursionlimit(100001)
(n, m) = map(int, input().split())
edges = [[] for _ in range(n)]
visited = [False] * n
for _ in range(m):
	(a, b) = map(int, input().split())
	la = len(edges[a - 1])
	lb = len(edges[b - 1])
	edges[a - 1].append([b - 1, lb])
	edges[b - 1].append([a - 1, la])

def dfs(p, v):
	visited[v] = True
	for (i, r) in edges[v]:
		if not visited[i] and r != -1 and (i != p):
			dfs(v, i)
	odd = False
	pr = -1
	for (i, r) in edges[v]:
		if i != p:
			if r != -1:
				edges[i][r][1] = -1
				odd = not odd
		else:
			pr = r
	if odd:
		edges[p][pr][1] = -1
if m % 2 == 1:
	print(-1)
else:
	dfs(-1, 0)
	for v in range(n):
		for (i, r) in edges[v]:
			if r >= 0:
				print(v + 1, i + 1)


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10 ** 5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right

def LI():
	return list(map(int, stdin.readline().split()))

def LF():
	return list(map(float, stdin.readline().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, stdin.readline().split()))

def II():
	return int(stdin.readline())

def IF():
	return float(stdin.readline())

def LS():
	return list(map(list, stdin.readline().split()))

def S():
	return list(stdin.readline().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

def A():
	n = II()
	a = LI()
	a.sort()
	x = list(set(a))
	if len(x) > 3:
		print('No')
	elif len(x) == 3:
		x.sort()
		x1 = bisect_right(a, x[0])
		x2 = bisect_right(a, x[1]) - bisect_left(a, x[1])
		x3 = bisect_right(a, x[2]) - bisect_left(a, x[2])
		if x[0] ^ x[1] ^ x[2] == 0 and x1 == x2 == x3:
			print('Yes')
		else:
			print('No')
	elif len(x) == 2:
		x1 = bisect_right(a, 0)
		x2 = bisect_right(a, x[1]) - bisect_left(a, x[1])
		if x1 * 2 == x2:
			print('Yes')
		else:
			print('No')
	elif len(x) == 1:
		if x[0] == 0:
			print('Yes')
		else:
			print('No')
	return

def B():
	(n, m) = LI()
	if m % 2:
		print(-1)
		return
	edg = [[] for _ in range(n)]
	ins = defaultdict(int)
	dag = defaultdict(int)
	for _ in range(m):
		(a, b) = LI_()
		edg[a].append(b)
		edg[b].append(a)
		dag[min(a, b), max(a, b)] = 1
		ins[min(a, b)] ^= 1
	for i in range(n):
		if ins[i] % 2:
			c = defaultdict(lambda : [inf, None])
			q = deque()
			q.append(i)
			c[i] = [0, -1]
			while ins[i] % 2:
				now = q.popleft()
				for k in edg[now]:
					if c[k][0] <= c[now][0]:
						continue
					c[k] = [c[now][0] + 1, now]
					if ins[k] % 2:
						a = k
						while a != i:
							b = c[a][1]
							dag[min(a, b), max(a, b)] ^= 1
							a = b
						ins[i] ^= 1
						ins[k] ^= 1
						break
					else:
						q.append(k)
	for (el1, el2) in dag.items():
		(e1, e2) = el1
		if el2:
			print(e1 + 1, e2 + 1)
		else:
			print(e2 + 1, e1 + 1)
	return

def C():
	return

def D():
	return

def E():
	return

def F():
	return

def G():
	return

def H():
	return
B()


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
EDGE = [list(map(int, input().split())) for i in range(M)]
if M % 2 != 0:
	print(-1)
	sys.exit()
E = [set() for i in range(N + 1)]
for (x, y) in EDGE:
	E[x].add(y)
	E[y].add(x)
ECOUNT = [0] * (N + 1)
from collections import deque
E_tree = [set() for i in range(N + 1)]
Q = deque()
Q.append(1)
check = [0] * (N + 1)
check[1] = 1
TOP = []
while Q:
	x = Q.pop()
	TOP.append(x)
	for to in E[x]:
		if check[to] == 0:
			Q.append(to)
			E_tree[x].add(to)
			E_tree[to].add(x)
			check[to] = 1
ECOUNT = [0] * (N + 1)
for (x, y) in EDGE:
	if x in E_tree[y]:
		continue
	print(x, y)
	ECOUNT[x] += 1
for p in TOP[::-1][:-1]:
	q = list(E_tree[p])[0]
	if ECOUNT[p] % 2 == 0:
		print(q, p)
		ECOUNT[q] += 1
	else:
		print(p, q)
	E_tree[q].remove(p)


import sys
sys.setrecursionlimit(pow(10, 6))
(n, m) = map(int, input().split())
graph = [[] for _ in range(n)]
dgraph = [[] for _ in range(n)]
edges = [[] for _ in range(n)]
eds = set()
visited = [False for i in range(n)]

def spanning_tree(i):
	if visited[i]:
		return
	visited[i] = True
	for to in graph[i]:
		if not visited[to]:
			edges[i].append(to)
			eds.add((i, to))
			spanning_tree(to)

def const_dgraph(i):
	ce = 0
	for to in edges[i]:
		c = const_dgraph(to)
		if c == 0:
			dgraph[i].append(to)
		else:
			dgraph[to].append(i)
	return len(dgraph[i]) % 2
if m % 2 == 1:
	print(-1)
else:
	for _ in range(m):
		(a, b) = map(int, input().split())
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
	spanning_tree(0)
	for (i, g) in enumerate(graph):
		for to in g:
			if (i, to) not in eds and (to, i) not in eds:
				dgraph[i].append(to)
				eds.add((i, to))
	visited = [False for _ in range(n)]
	const_dgraph(0)
	if len(dgraph[0]) % 2 == 1:
		print(-1)
	else:
		for (i, g) in enumerate(dgraph):
			for to in g:
				print('%d %d' % (i + 1, to + 1))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
if m % 2:
	print(-1)
else:
	G = [[] for _ in range(n + 1)]
	par = [-1] * (n + 1)
	ch = [[] for _ in range(n + 1)]
	seen = [False] * (n + 1)
	used = set()
	C = [0] * (n + 1)
	for _ in range(m):
		(a, b) = map(int, input().split())
		G[a].append(b)
		G[b].append(a)
	stack = [1]
	seen[1] = True
	while stack:
		v = stack.pop()
		for nv in G[v]:
			if seen[nv]:
				if par[v] != nv:
					if (v, nv) not in used:
						used.add((v, nv))
						used.add((nv, v))
						print(v, nv)
						C[v] ^= 1
			else:
				seen[nv] = True
				par[nv] = v
				ch[v].append(nv)
				stack.append(nv)

	def bottom_up(v):
		for nv in ch[v]:
			bottom_up(nv)
		if v == 1:
			return
		if C[v]:
			C[v] ^= 1
			print(v, par[v])
		else:
			C[par[v]] ^= 1
			print(par[v], v)
	bottom_up(1)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
(n, m) = [int(i) for i in readline().split()]
if m % 2:
	print(-1)
	exit()
g = [[] for _ in range(n)]
for i in range(m):
	(a, b) = [int(i) for i in readline().split()]
	g[a - 1].append((b - 1, i))
	g[b - 1].append((a - 1, i))
used = [0] * m
usedp = [0] * n

def dfs(v):
	res = 0
	for (c, i) in g[v]:
		if used[i] == 1:
			continue
		used[i] = 1
		if usedp[c] == 1:
			res += 1
			print(v + 1, c + 1)
			continue
		usedp[c] = 1
		p = dfs(c)
		if p % 2 == 1:
			print(v + 1, c + 1)
		else:
			print(c + 1, v + 1)
		res += p
	return res + 1
for i in range(n):
	dfs(i)


def main():
	(n, m) = map(int, input().split())
	if m % 2:
		print(-1)
		return
	ab = [list(map(int, input().split())) for _ in [0] * m]
	g = [set() for _ in [0] * n]
	[g[a - 1].add(b - 1) for (a, b) in ab]
	[g[b - 1].add(a - 1) for (a, b) in ab]
	ab = [(a - 1, b - 1) for (a, b) in ab]

	def Kruskal(n, abc, weight=False):

		class unionfind:

			def __init__(self, size):
				self.size = size
				self.tree_root = list(range(self.size))
				self.tree_depth = [1] * self.size

			def root(self, index):
				temp_list = []
				temp = self.tree_root[index]
				while index != temp:
					temp_list.append(index)
					index = temp
					temp = self.tree_root[index]
				for i in temp_list:
					self.tree_root[i] = index
				return index

			def unite(self, index1, index2):
				r1 = self.root(index1)
				r2 = self.root(index2)
				if r1 != r2:
					(d1, d2) = (self.tree_depth[r1], self.tree_depth[r2])
					if d1 <= d2:
						self.tree_root[r1] = r2
						self.tree_depth[r2] = max(d1 + 1, d2)
					else:
						self.tree_root[r2] = r1
						self.tree_depth[r1] = max(d2 + 1, d1)

			def same(self, index1, index2):
				r1 = self.root(index1)
				r2 = self.root(index2)
				return r1 == r2

			def component(self):
				return len({self.root(i) for i in range(self.size)})
		uf = unionfind(n)
		ret = []
		if weight:
			abc.sort(key=lambda x: x[2])
		for (a, b, *c) in abc:
			if not uf.same(a, b):
				ret.append([a, b])
				uf.unite(a, b)
		return ret
	t = Kruskal(n, ab)
	g2 = [set() for _ in [0] * n]
	[g2[a].add(b) for (a, b) in t]
	[g2[b].add(a) for (a, b) in t]
	root = 0
	d = [-1] * n
	d[root] = 0
	q = [root]
	cnt = 0
	while q:
		cnt += 1
		qq = []
		while q:
			i = q.pop()
			for j in g2[i]:
				if d[j] == -1:
					d[j] = cnt
					qq.append(j)
		q = qq
	d2 = sorted([(i, j) for (i, j) in enumerate(d)], key=lambda x: -x[1])
	now = [0] * n
	ans = []
	for (i, j) in d2:
		remove_list = []
		for k in g[i]:
			if k not in g2[i]:
				now[i] += 1
				ans.append((i + 1, k + 1))
				remove_list += [(i, k), (k, i)]
		for (k, l) in remove_list:
			g[k].remove(l)
	for (i, j) in d2[:-1]:
		k = g[i].pop()
		g[k].remove(i)
		if now[i] % 2:
			now[i] += 1
			ans.append((i + 1, k + 1))
		else:
			now[k] -= 1
			ans.append((k + 1, i + 1))
	for i in ans:
		print(*i)
main()


from bisect import bisect
(N, M) = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(M)]
if M % 2 == 1:
	print(-1)
	exit()
inv_ABs = [dict() for _ in range(N + 1)]
for (i, (A, B)) in enumerate(ABs):
	inv_ABs[A][B] = i
	inv_ABs[B][A] = i
reverse_ABs = [False] * M
iseven = [True] * (N + 1)
for (A, B) in ABs:
	if not iseven[B]:
		iseven[B] = True
		reverse_ABs[inv_ABs[A][B]] = True
	else:
		iseven[A] = not iseven[A]
start = 1
stack = [start]
parent = [0] * (N + 1)
parent[start] = start
et = []
while stack:
	v = stack.pop()
	if v >= 0:
		et.append(v)
		for nv in inv_ABs[v]:
			if parent[nv] == 0:
				parent[nv] = v
				stack.append(~nv)
				stack.append(nv)
	else:
		et.append(parent[~v])
imos = [0] * (len(et) + 1)
odd_nodes = set((i for (i, e) in enumerate(iseven) if not e))
for (i, v) in enumerate(et):
	if v in odd_nodes:
		odd_nodes.remove(v)
		imos[i] += 1
	imos[i + 1] += imos[i]
for i in range(len(et) - 1):
	if imos[i] % 2 == 1:
		reverse_ABs[inv_ABs[et[i]][et[i + 1]]] = not reverse_ABs[inv_ABs[et[i]][et[i + 1]]]
for (rflg, (A, B)) in zip(reverse_ABs, ABs):
	if rflg:
		print(B, A)
	else:
		print(A, B)


import sys
readline = sys.stdin.readline
write = sys.stdout.write
sys.setrecursionlimit(2 * 10 ** 6)

class UF:

	def __init__(self, num):
		self.par = [-1] * num
		self.size = [1] * num

	def find(self, x):
		if self.par[x] < 0:
			return x
		else:
			x = self.par[x]
			return self.find(x)

	def union(self, x, y):
		rx = self.find(x)
		ry = self.find(y)
		if rx != ry:
			if self.par[rx] < self.par[ry]:
				self.par[ry] = rx
				self.size[rx] += self.size[ry]
			elif self.par[rx] > self.par[ry]:
				self.par[rx] = ry
				self.size[ry] += self.size[rx]
			else:
				self.par[rx] -= 1
				self.par[ry] = rx
				self.size[rx] += self.size[ry]
			return True
		return False

def getpar(Edge, p):
	N = len(Edge)
	par = [0] * N
	par[0] = -1
	par[p] - 1
	stack = [p]
	visited = set([p])
	while stack:
		vn = stack.pop()
		for vf in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			stack.append(vf)
	return par

def topological_sort_tree(E, r):
	Q = [r]
	L = []
	visited = set([r])
	while Q:
		vn = Q.pop()
		L.append(vn)
		for vf in E[vn]:
			if vf not in visited:
				visited.add(vf)
				Q.append(vf)
	return L
(N, M) = map(int, readline().split())
Edge = []
for _ in range(M):
	(a, b) = map(int, readline().split())
	a -= 1
	b -= 1
	Edge.append((a, b))
tr = [[] for _ in range(N)]
ans = []
eo = [0] * N
T = UF(N)
for (a, b) in Edge:
	if T.union(a, b):
		tr[a].append(b)
		tr[b].append(a)
	else:
		ans.append((a + 1, b + 1))
		eo[a] ^= 1
L = topological_sort_tree(tr, 0)
P = getpar(tr, 0)
for l in L[1:][::-1]:
	if eo[l]:
		ans.append((l + 1, P[l] + 1))
	else:
		ans.append((P[l] + 1, l + 1))
		eo[P[l]] ^= 1
if M % 2 == 0:
	for (a, b) in ans:
		write('{} {}\n'.format(a, b))
else:
	write('-1\n')


import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 6)

def main():
	input = sys.stdin.readline
	(N, M) = map(int, input().split())
	if M % 2 == 1:
		print(-1)
		return 0
	G = [[] for _ in range(N + 1)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		G[a].append(b)
		G[b].append(a)
	heap = []
	dist = [N] * (N + 1)
	dist[1] = 0
	d = 0
	q = deque()
	q.append(1)
	while len(q) > 0:
		d += 1
		q_ = deque()
		while len(q) > 0:
			a = q.popleft()
			for b in G[a]:
				if dist[b] > d:
					dist[b] = d
					q_.append(b)
					heappush(heap, (-d, b))
		q = q_
	cnt = [0] * (N + 1)
	visited = [False] * (N + 1)
	ans = []
	while len(heap) > 0:
		(_, a) = heappop(heap)
		visited[a] = True
		for b in G[a]:
			if visited[b]:
				continue
			if cnt[a] % 2 == 1:
				ans.append((a, b))
				cnt[a] += 1
			else:
				ans.append((b, a))
				cnt[b] += 1
	for (a, b) in ans:
		print('{} {}'.format(a, b))
	exit()
main()


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
(N, M, *AB) = map(int, open(0).read().split())
if M % 2 == 1:
	print(-1)
	quit()
E = [[] for _ in range(N + 1)]
for (i, (a, b)) in enumerate(zip(*[iter(AB)] * 2)):
	E[a].append((b, i))
	E[b].append((a, i))
used = [False] * M
visited = [False] * (N + 1)
ans = []

def dfs(cur, par):
	cnt = 0
	for (nxt, c) in E[cur]:
		if not visited[nxt]:
			visited[nxt] = True
			dfs(nxt, cur)
		if not used[c]:
			cnt += 1
	for (nxt, c) in E[cur]:
		if cnt % 2 == 1 and nxt == par:
			continue
		if not used[c]:
			used[c] = True
			ans.append((cur, nxt))
dfs(1, -1)
for (c, d) in ans:
	print(c, d)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
(n, m) = map(int, input().split())
if m % 2:
	print(-1)
	exit(0)
l = [tuple(map(int1, input().split())) for _ in range(m)]
G = [list() for _ in range(n)]
ps = [-1] * n
tot = [0] * n

def find(x):
	if ps[x] < 0:
		return x
	ps[x] = find(ps[x])
	return ps[x]

def unite(u, v):
	u = find(u)
	v = find(v)
	if ps[u] > ps[v]:
		(u, v) = (v, u)
	ps[u] += ps[v]
	ps[v] = u
	return

def same(u, v):
	return find(u) == find(v)
for (u, v) in l:
	if same(u, v):
		print(u + 1, v + 1)
		tot[u] += 1
	else:
		G[u].append(v)
		G[v].append(u)
		unite(u, v)

def dfs(v, p):
	for u in G[v]:
		if u == p:
			continue
		dfs(u, v)
	if p >= 0:
		if tot[v] % 2:
			print(v + 1, p + 1)
			tot[v] += 1
		else:
			print(p + 1, v + 1)
			tot[p] += 1
	return
dfs(0, -1)


import sys
from collections import deque
sys.setrecursionlimit(200000)
(n, m) = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
if m & 1:
	print(-1)
	sys.exit()
Tr = [0] * n
Q = deque()
Q.append(0)
Tr[0] = 1
TrE = [[] for _ in range(n)]
P = [-1] * n
Leaf = []
while Q:
	v = Q.popleft()
	leaf_v = True
	for u in G[v]:
		if not Tr[u]:
			Tr[u] = 1
			P[u] = v
			TrE[v].append(u)
			Q.append(u)
			leaf_v = False
	if leaf_v:
		Leaf.append(v)
out = [0] * n
D = set()
for v in range(n):
	for u in G[v]:
		if (u, v) not in D and P[v] != u and (P[u] != v):
			D.add((v, u))
			out[v] ^= 1

def dfs(x=0, parent=-1):
	for y in TrE[x]:
		if y == parent:
			continue
		dfs(y, x)
		if out[y]:
			D.add((y, x))
			out[y] ^= 1
		else:
			D.add((x, y))
			out[x] ^= 1
dfs()
for (u, v) in D:
	print(u + 1, v + 1)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
(N, M) = map(int, input().split())
edge = [[] for i in range(0, N)]
dedge = [0 for i in range(0, N)]
data = []
dic = {}
for i in range(M):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
	dedge[a - 1] += 1
	dic[a - 1, b - 1] = 0
	dic[b - 1, a - 1] = 0
	dic[a - 1, b - 1] = i
	dic[b - 1, a - 1] = i
	data.append([a - 1, b - 1, 0])
if M % 2 == 1:
	print(-1)
	exit()
ans = [0 for i in range(N)]
treeedge = [[] for i in range(0, N)]
visit = set([0])
q = set([0])
sub = set([])
while q:
	while q:
		x = q.pop()
		for i in edge[x]:
			if i not in visit:
				treeedge[x].append(i)
				treeedge[i].append(x)
				visit.add(i)
				sub.add(i)
		if not q:
			q = sub
			sub = set([])
			break

def dfs(v, pv):
	if len(treeedge[v]) == 1 and v != 0:
		ans[v] = (dedge[v] % 2, pv)
		return dedge[v] % 2
	A = dedge[v] % 2
	for i in treeedge[v]:
		if i != pv:
			A += dfs(i, v)
	ans[v] = (A % 2, pv)
	return ans[v][0]
dfs(0, -1)
for i in range(1, N):
	(val, parent) = ans[i]
	if val == 1:
		index = dic[i, parent]
		data[index][2] = 1
for i in range(M):
	(a, b, val) = data[i]
	if val == 0:
		print(a + 1, b + 1)
	else:
		print(b + 1, a + 1)


import sys
sys.setrecursionlimit(200000)
(N, M) = map(int, input().split())
lisN = [[] for i in range(N)]
xorlis = [0] * N
AB = []
if M % 2 == 1:
	print(-1)
	sys.exit()
for i in range(M):
	(a, b) = map(int, input().split())
	AB.append([a, b])
	a -= 1
	b -= 1
	lisN[a].append([b, i])
	lisN[b].append([a, i])
	xorlis[b] ^= 1
visited = [False] * N

def dfs(now):
	visited[now] = True
	for (nex, eind) in lisN[now]:
		if visited[nex]:
			continue
		cat = dfs(nex)
		if cat != 0:
			xorlis[nex] ^= 1
			xorlis[now] ^= 1
			t = AB[eind][1]
			AB[eind][1] = AB[eind][0]
			AB[eind][0] = t
	return xorlis[now]
dfs(0)
if 1 in xorlis:
	print(-1)
	sys.exit()
else:
	for (i, j) in AB:
		print(j, i)


from collections import deque

class UnionFind:
	n = 1
	par = [0]
	rnk = [0]

	def __init__(self, size):
		self.n = size
		self.par = [i for i in range(self.n)]
		self.rnk = [0 for i in range(self.n)]

	def find(self, vertex1):
		if self.par[vertex1] == vertex1:
			return vertex1
		else:
			self.par[vertex1] = self.find(self.par[vertex1])
			return self.par[vertex1]

	def unite(self, vertex1, vertex2):
		vertex1 = self.find(vertex1)
		vertex2 = self.find(vertex2)
		if vertex1 == vertex2:
			return
		if self.rnk[vertex1] < self.rnk[vertex2]:
			self.par[vertex1] = vertex2
		else:
			self.par[vertex2] = vertex1
			if self.rnk[vertex1] == self.rnk[vertex2]:
				self.rnk[vertex1] += 1

	def same(self, vetrex1, vertex2):
		return self.find(vetrex1) == self.find(vertex2)
(N, M) = map(int, input().split())
if M % 2 == 1:
	print(-1)
	exit()
edges = []
tree = []
G = UnionFind(N)
H = [[] for i in range(N)]
T = [[] for i in range(N)]
for i in range(M):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	if G.same(a, b):
		edges.append((a, b))
		H[a].append(b)
	else:
		tree.append((a, b))
		G.unite(a, b)
		T[a].append(b)
		T[b].append(a)
q = deque([0])
reached = [0 for i in range(N)]
search = deque([])
parents = [-1 for i in range(N)]
while len(q) > 0:
	r = q.popleft()
	reached[r] = 1
	for p in T[r]:
		if reached[p] == 0:
			q.append(p)
			parents[p] = r
			search.appendleft(p)
for i in range(N - 1):
	v = search.popleft()
	p = parents[v]
	if len(H[v]) % 2 == 0:
		H[p].append(v)
	else:
		H[v].append(p)
for i in range(N):
	for j in H[i]:
		print(i + 1, j + 1)


import sys
input = sys.stdin.readline

def main():
	(N, M) = map(int, input().split())
	graph = [[] for _ in range(N)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		graph[a - 1].append(b - 1)
		graph[b - 1].append(a - 1)
	if M % 2 == 1:
		print(-1)
		return
	q = [0]
	checked = [False] * N
	checked[0] = True
	search_seq = [0]
	while q:
		qq = []
		for p in q:
			for np in graph[p]:
				if not checked[np]:
					checked[np] = True
					qq.append(np)
					search_seq.append(np)
		q = qq
	evenOrOdd = []
	for n in range(N):
		evenOrOdd.append(len(graph[n]) % 2)
	searched = [False] * N
	ans = []
	for p in reversed(search_seq):
		evens = []
		odds = []
		for np in graph[p]:
			if not searched[np]:
				if evenOrOdd[np]:
					odds.append(np)
				else:
					evens.append(np)
		if not odds and (not evens):
			break
		if evenOrOdd[p] == 1:
			if odds:
				np = odds.pop()
				ans.append((np, p))
			else:
				np = evens.pop()
				ans.append((np, p))
		for np in odds:
			ans.append((p, np))
			evenOrOdd[np] = 0
		for np in evens:
			ans.append((p, np))
			evenOrOdd[np] = 1
		searched[p] = True
	for (a1, a2) in ans:
		print(a1 + 1, a2 + 1)
	return
main()


from collections import defaultdict
from collections import deque
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
if M % 2 == 1:
	print(-1)
	exit(0)
tree = defaultdict(list)
for i in range(M):
	temp = list(map(int, input().split()))
	tree[temp[0]].append([temp[1], i])
	tree[temp[1]].append([temp[0], i])
usede = [0] * M
visitedv = [0] * (N + 1)
res = []

def dfs(prev, v):
	global usede
	global visitedv
	global res
	if visitedv[v] == 1:
		return
	visitedv[v] = 1
	movable = 0
	for l in tree[v]:
		w = l[0]
		i = l[1]
		dfs(v, w)
		if usede[i] == 0:
			movable += 1
	for l in tree[v]:
		w = l[0]
		i = l[1]
		if w == prev and movable % 2 == 1:
			continue
		if usede[i] == 0:
			res.append((v, w))
			usede[i] = 1
dfs(0, 1)
for v in res:
	print(v[0], v[1])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
(N, M) = map(int, input().split())
if M % 2 == 0:
	vec = [[] for _ in range(N)]
	for _ in range(M):
		(A, B) = map(int, input().split())
		vec[A - 1].append(B - 1)
		vec[B - 1].append(A - 1)
	visited = [False] * N
	CD = [[] for _ in range(N)]

	def dfs(cur, pre):
		for nex in vec[cur]:
			if nex == pre:
				continue
			if not visited[nex]:
				visited[nex] = True
				dfs(nex, cur)
			elif not cur in CD[nex]:
				CD[cur].append(nex)
		if pre != -1:
			if len(CD[cur]) % 2 == 0:
				CD[pre].append(cur)
			else:
				CD[cur].append(pre)
	visited[0] = True
	dfs(0, -1)
	for i in range(N):
		for j in CD[i]:
			print(i + 1, j + 1)
else:
	print(-1)


import sys, collections
sys.setrecursionlimit(10 ** 7)
(n, m) = map(int, input().split())
vertices_in = [set() for _ in range(n + 1)]
vertices_out = [set() for _ in range(n + 1)]
nodes = [1] * (n + 1)
done = set()
use = set()
dq = collections.deque([])
for i in range(m):
	(a, b) = map(int, sys.stdin.readline().split())
	vertices_in[a].add(b)
	vertices_in[b].add(a)
dq.append(1)
order = [1]

def factory(num):
	for v in vertices_in[num]:
		if v not in done:
			done.add(v)
			factory(v)
	for v in vertices_in[num]:
		if num not in vertices_out[v]:
			vertices_out[num].add(v)
			use.add(v)
	if len(vertices_out[num]) % 2 != 0:
		for v in vertices_out[num]:
			if nodes[v]:
				vertices_out[num].remove(v)
				use.remove(v)
				break
	nodes[num] = 0
if m % 2 == 1:
	print(-1)
else:
	factory(1)
	for i in range(1, n + 1):
		for v in vertices_out[i]:
			print(i, v)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
if M & 1:
	print(-1)
	exit()
AB = [[int(x) for x in input().split()] for _ in range(M)]
graph = [[] for _ in range(N + 1)]
for (a, b) in AB:
	graph[a].append(b)
	graph[b].append(a)
tree = [set() for _ in range(N + 1)]
visited = [False] * (N + 1)
q = [1]
while q:
	x = q.pop()
	for y in graph[x]:
		if visited[y]:
			continue
		visited[y] = True
		tree[x].add(y)
		tree[y].add(x)
		q.append(y)
answer = []
out_deg = [0] * (N + 1)
for (a, b) in AB:
	if b in tree[a]:
		continue
	answer.append('{} {}'.format(a, b))
	out_deg[a] += 1

def dfs(x=1, parent=None):
	for y in tree[x]:
		if y == parent:
			continue
		dfs(y, x)
		if out_deg[y] & 1:
			answer.append('{} {}'.format(y, x))
			out_deg[y] += 1
		else:
			answer.append('{} {}'.format(x, y))
			out_deg[x] += 1
dfs()
print('\n'.join(answer))


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def li():
	return map(int, stdin.readline().split())

def li_():
	return map(lambda x: int(x) - 1, stdin.readline().split())

def lf():
	return map(float, stdin.readline().split())

def ls():
	return stdin.readline().split()

def ns():
	return stdin.readline().rstrip()

def lc():
	return list(ns())

def ni():
	return int(stdin.readline())

def nf():
	return float(stdin.readline())
(n, m) = li()
edge = dict()
graph = [[] for _ in range(n)]
visited = [False] * n
par = [-1] * n
outs = [0] * n
for _ in range(m):
	(a, b) = li_()
	edge[a, b] = 0
	edge[b, a] = 0
	graph[a].append(b)
	graph[b].append(a)

def dfs(graph, visited, par, root, cur):
	for nex in graph[cur]:
		if visited[nex]:
			continue
		else:
			visited[nex] = True
			par[nex] = cur
			dfs(graph, visited, par, root, nex)
	if cur == root:
		return
	for neighbor in graph[cur]:
		if neighbor == par[cur]:
			continue
		if edge[cur, neighbor] != 0:
			continue
		edge[cur, neighbor] = 1
		edge[neighbor, cur] = -1
		outs[cur] += 1
	if outs[cur] % 2:
		edge[cur, par[cur]] = 1
		edge[par[cur], cur] = -1
		outs[cur] += 1
	else:
		edge[cur, par[cur]] = -1
		edge[par[cur], cur] = 1
		outs[par[cur]] += 1
if m % 2:
	print(-1)
else:
	visited[0] = True
	dfs(graph, visited, par, 0, 0)
	for ((src, dst), val) in edge.items():
		if val == 1:
			print(src + 1, dst + 1)


def MI():
	return map(int, input().split())

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]
(n, m) = MI()
g = [[] for i in range(n)]
v = [0] * n
f = [0] * n
e = []
for i in range(m):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a].append(b)
	g[b].append(a)
	e.append((a, b))

def get_tree(st):
	(p, q) = ([], [])
	q.append(st)
	v[st] = 1
	while q:
		cur = q.pop()
		for nb in g[cur]:
			if v[nb] != 1:
				q.append(nb)
				p.append((cur, nb))
				v[nb] = 1
	return p

def solve():
	tr = get_tree(0)
	st = set(tr)
	rt = []
	for (a, b) in e:
		if (a, b) in st or (b, a) in st:
			pass
		else:
			rt.append((a, b))
			f[a] = 1 - f[a]
	for (a, b) in tr[::-1]:
		if f[b] == 0:
			rt.append((a, b))
			f[a] = 1 - f[a]
		else:
			rt.append((b, a))
			f[b] = 1 - f[b]
	return rt
if m % 2 == 1:
	print(-1)
else:
	for (a, b) in solve():
		print(a + 1, b + 1)


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():
	n = I()
	a = LI()
	if sum(a) == 0:
		print('Yes')
		return
	if n % 3 != 0:
		print('No')
		return
	d = defaultdict(lambda : 0)
	for i in a:
		d[i] += 1
	if len(list(d.items())) == 2:
		if d[0] == n // 3:
			print('Yes')
			return
		else:
			print('No')
			return
	k = 0
	for (i, j) in d.items():
		k ^= i
		if j != n // 3:
			print('No')
			return
	if not k:
		print('Yes')
		return
	print('No')
	return

def B():

	def dfs(x, d):
		for y in v[x]:
			if d[y]:
				d[y] = 0
				dfs(y, d)
				if f[y]:
					ans[min(x, y), max(x, y)] ^= 1
					f[x] ^= 1
					f[y] ^= 1
	(n, m) = LI()
	ans = defaultdict(int)
	f = [0] * (n + 1)
	v = [[] for i in range(n + 1)]
	for i in range(m):
		(a, b) = LI()
		ans[min(a, b), max(a, b)] = 1
		v[a].append(b)
		v[b].append(a)
		f[min(a, b)] ^= 1
	if m % 2:
		print(-1)
		return
	d = [1] * (n + 1)
	d[1] = 0
	dfs(1, d)
	for (v, i) in ans.items():
		if i:
			print(*v)
		else:
			print(*v[::-1])
	return

def C():
	n = I()
	p = [1 << i for i in range(100)]
	if n in p:
		print('No')
		quit()
	if n + 1 in p:
		print('Yes')
		for i in range(1, 2 * n):
			print(i, i + 1)
		quit()
	ans = []
	for i in range(1, 3):
		ans.append((i, i + 1))
	ans.append((3, n + 1))
	for i in range(1, 3):
		ans.append((i + n, i + n + 1))
	u = 1
	d = 1
	for i in range(2, n // 2 + n % 2):
		ans.append((u, 2 * i))
		ans.append((d, 2 * i + 1))
		ans.append((2 * i, 2 * i + n + 1))
		ans.append((2 * i + 1, 2 * i + n))
		u = 2 * i + n + 1
		d = 2 * i + n
	if n % 2:
		print('Yes')
		for (i, j) in ans:
			print(i, j)
	else:
		ans.append((n - 1, n))
		for i in range(n):
			if p[i] & n:
				break
		ans.append((p[i + 1] - 2, 2 * n))
		print('Yes')
		for (i, j) in ans:
			print(i, j)
	return

def D():
	n = I()
	return

def E():
	n = I()
	return

def F():
	n = I()
	return
B()


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.readline

def solve(p, v, rs):
	als = G[v]
	cs = g[v]
	c = 0
	for u in als:
		if u in cs:
			c += solve(v, u, rs)
		elif u != p:
			if v < u:
				c += 1
			rs.add((min(u, v), max(u, v)))
	if p == None:
		return
	elif c % 2 != 0:
		rs.add((v, p))
		return 0
	else:
		rs.add((p, v))
		return 1
(N, M) = map(int, readline().split())
if M % 2 != 0:
	print(-1)
else:
	G = defaultdict(set)
	for v in range(M):
		(a, b) = map(int, readline().split())
		G[a].add(b)
		G[b].add(a)
	stack = [1]
	vs = set([1])
	g = defaultdict(set)
	counter = 1
	while True:
		v = stack.pop()
		for u in G[v]:
			if u in vs:
				continue
			vs.add(u)
			g[v].add(u)
			stack.append(u)
			counter += 1
		if counter == N:
			break
	rs = set()
	solve(None, 1, rs)
	for r in rs:
		print(r[0], r[1])


import sys
sys.setrecursionlimit(1000000)
(nVertices, nEdges) = map(int, input().split())
edges = [[] for _ in range(nVertices + 1)]
for _ in range(nEdges):
	(u, v) = map(int, input().split())
	edges[u].append(v)
	edges[v].append(u)
if nEdges & 1 == 1:
	print(-1)
	exit()

def dfs(v):
	visited[v] = True
	for next in edges[v]:
		if not visited[next]:
			mst[v].add(next)
			mst[next].add(v)
			dfs(next)

def dfs2(par, v):
	for child in mst[v]:
		if child != par:
			dfs2(v, child)
	if par == 0:
		return
	if len(out[v]) & 1 == 1:
		out[v].add(par)
	else:
		out[par].add(v)
mst = [set() for _ in range(nVertices + 1)]
visited = [False] * (nVertices + 1)
dfs(1)
out = [set() for _ in range(nVertices + 1)]
for u in range(1, nVertices + 1):
	for v in edges[u]:
		if v not in mst[u] and u not in out[v]:
			out[u].add(v)
dfs2(0, 1)
for u in range(1, nVertices + 1):
	for v in out[u]:
		print(u, v)


import sys
sys.setrecursionlimit(10 ** 9)

def dfs1(v):
	for u in g[v]:
		if checked[u] == 0:
			checked[u] = 1
			g2[v].append(u)
			g3[v].append(u)
			g3[u].append(v)
			dfs1(u)

def dfs2(v):
	for u in g2[v]:
		if checked[u] == 0:
			checked[u] = 1
			dfs2(u)
			if cnt[u] % 2 == 1:
				ans.append((u, v))
				cnt[u] += 1
			else:
				ans.append((v, u))
				cnt[v] += 1
(n, m) = map(int, input().split())
g = [[] for _ in range(n + 1)]
g2 = [[] for _ in range(n + 1)]
g3 = [[] for _ in range(n + 1)]
cnt = [0] * (n + 1)
ans = []
ansset = set()
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
if m % 2 == 1:
	print(-1)
else:
	checked = [0] * (n + 1)
	checked[1] = 1
	dfs1(1)
	for v in range(1, n + 1):
		for u in g[v]:
			if u not in g3[v]:
				if (u, v) not in ansset:
					ans.append((v, u))
					ansset.add((v, u))
					cnt[v] += 1
	checked = [0] * (n + 1)
	checked[1] = 1
	dfs2(1)
	for (v, u) in ans:
		print(v, u)


class Bridge:

	def __init__(self, nodeA, nodeB):
		self.edges = [BridgeEdge(nodeA, self), BridgeEdge(nodeB, self)]
		nodeA.addEdge(self.edges[1])
		nodeB.addEdge(self.edges[0])
		self.dir = True
		self.vec = None

	def __repr__(self):
		return str((self.vec, self.dir))

class BridgeEdge:

	def __init__(self, node, edge):
		self.edge = edge
		self.node = node

	def another(self):
		return self.edge.edges[1 if self.edge.edges[0] == self else 0]

class Node:

	def __init__(self, id):
		self.id = id
		self.bridges = []
		self.parent = None
		self.judge = True

	def addEdge(self, bridgeEdge):
		self.bridges.append(bridgeEdge)

	def __repr__(self):
		return str((self.id, None if self.parent is None else self.parent.node.id, self.judge))
(N, M) = map(int, input().split())
nodes = [Node(i) for i in range(N + 1)]
bridges = []
for (A, B) in (map(int, input().split()) for _ in range(M)):
	bridges.append(Bridge(nodes[A], nodes[B]))
s = [(0, nodes[1])]
idx = 0
while len(s) > 0:
	(level, cur) = s.pop()
	nxtlevel = level + 1
	for nxt in cur.bridges:
		if nxt.edge.vec is None:
			cur.judge ^= True
			nxt.edge.vec = (cur.id, nxt.node.id)
			if nxt.node.parent is None:
				nxt.node.parent = nxt.another()
				s.append((nxtlevel, nxt.node))
	if len(s) > 0:
		nl = s[-1][0]
	else:
		nl = 1
	while level >= nl:
		if not cur.judge:
			cur.judge ^= True
			cur.parent.node.judge ^= True
			cur.parent.edge.dir ^= True
		level -= 1
		cur = cur.parent.node
if all((node.judge for node in nodes[1:])):
	for br in bridges:
		if br.dir:
			print('{} {}'.format(br.vec[0], br.vec[1]))
		else:
			print('{} {}'.format(br.vec[1], br.vec[0]))
else:
	print('-1')


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
(n, m) = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
if m % 2 == 1:
	print(-1)
	exit()
ans = []
depth = [-1] * n
deg = [0] * n

def dfs(v, pr):
	for nv in g[v]:
		if nv == pr:
			continue
		if depth[nv] != -1:
			if depth[nv] < depth[v]:
				ans.append((v, nv))
				deg[v] += 1
		else:
			depth[nv] = depth[v] + 1
			dfs(nv, v)
			if deg[nv] % 2 == 0:
				ans.append((v, nv))
				deg[v] += 1
			else:
				ans.append((nv, v))
				deg[nv] += 1
depth[0] = 0
dfs(0, -1)
for (i, j) in ans:
	print(i + 1, j + 1)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
G = [set() for _ in range(N + 1)]
for _ in range(M):
	(A, B) = map(int, input().split())
	G[A].add(B)
	G[B].add(A)
if M % 2 == 1:
	print(-1)
	exit()
G2 = [set() for _ in range(N + 1)]
parent = [0] * (N + 1)
depth = [-1] * (N + 1)
depth[1] = 0
stack = [1]
while stack:
	v = stack.pop()
	if len(G[v]) > 0 and v != 1:
		depth[v] = depth[parent[v]] + 1
	for c in G[v]:
		G2[v].add(c)
		parent[c] = v
		if v in G[c]:
			G[c].remove(v)
		stack.append(c)
	G[v] = set()
nodes = sorted(list(range(1, N + 1)), key=lambda v: -depth[v])
ans = []
for v in nodes:
	for c in G2[v]:
		ans.append((v, c))
	if len(G2[v]) % 2 == 1:
		p = parent[v]
		ans.append((v, p))
		G2[p].remove(v)
for (u, v) in ans:
	print(u, v)


(n, m) = map(int, input().split())
edges = []
parity = [0] * n
di = {}
C = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = [int(x) - 1 for x in input().split()]
	C[a].append(b)
	C[b].append(a)
	edges.append((a, b))
	parity[b] ^= 1
	di[a, b] = 0
if sum(parity) % 2 == 1:
	print(-1)
else:
	parent = [-1] * n
	parent[0] = 0
	Q = [0]
	order = []
	for cur in Q:
		for neigh in C[cur]:
			if parent[neigh] == -1:
				order.append(neigh)
				parent[neigh] = cur
				Q.append(neigh)
	for v in reversed(order):
		if parity[v] == 1:
			u = v
			p = parent[u]
			if (u, p) not in di:
				(u, p) = (p, u)
			di[u, p] ^= 1
			parity[v] ^= 1
			parity[parent[v]] ^= 1
	for (a, b) in edges:
		if di[a, b] == 0:
			print(b + 1, a + 1)
		else:
			print(a + 1, b + 1)


import sys
(n, m) = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
lst = [set() for _ in range(n + 1)]
for (a, b) in edge:
	lst[a].add(b)
	lst[b].add(a)
if m % 2 == 1:
	print(-1)
	sys.exit()
check = [0] * (n + 1)
q = [1]
next_q = []
tree = [set() for _ in range(n + 1)]
top = [1]
while q:
	for oya in q:
		check[oya] = 1
		for ko in lst[oya]:
			if check[ko] == 0:
				check[ko] = 1
				top.append(ko)
				next_q.append(ko)
				tree[oya].add(ko)
				tree[ko].add(oya)
	q = next_q.copy()
	next_q = []
ecount = [0] * (n + 1)
for (a, b) in edge:
	if a in tree[b]:
		continue
	print(a, b)
	ecount[a] += 1
for i in top[::-1][:-1]:
	j = list(tree[i])[0]
	if ecount[i] % 2 == 0:
		print(j, i)
		ecount[j] += 1
	else:
		print(i, j)
		ecount[i] += 1
	tree[i].remove(j)
	tree[j].remove(i)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce
sys.setrecursionlimit(2147483647)
INF = float(10 ** 5)

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
(n, m) = LI()
G = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = LI()
	G[a - 1] += [b - 1]
	G[b - 1] += [a - 1]
par = [-2] * n
par[0] = -1
used = set()
cnt = [0] * n

def dfs(u):
	for v in G[u]:
		if v in used or par[u] == v:
			continue
		if par[v] != -2:
			print(u + 1, v + 1)
			cnt[u] ^= 1
		else:
			par[v] = u
			if dfs(v):
				print(v + 1, u + 1)
				cnt[v] ^= 1
			else:
				print(u + 1, v + 1)
				cnt[u] ^= 1
	used.add(u)
	if cnt[u]:
		return 1
if m % 2:
	print(-1)
else:
	dfs(0)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
if M % 2 != 0:
	print(-1)
	exit()
G = [[] for i in range(N)]
E = []
for i in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append(b)
	G[b].append(a)
	E.append((a, b))
visited = [False] * N
T = [set() for i in range(N)]
que = [0]
while que:
	u = que.pop()
	for w in G[u]:
		if visited[w]:
			continue
		visited[w] = True
		T[u].add(w)
		T[w].add(u)
		que.append(w)
ans = []
deg = [0] * N
for (a, b) in E:
	if b in T[a]:
		continue
	ans.append((a, b))
	deg[a] += 1

def dfs(u, p):
	for w in T[u]:
		if w == p:
			continue
		dfs(w, u)
		if deg[w] % 2 != 0:
			ans.append((w, u))
			deg[w] += 1
		else:
			ans.append((u, w))
			deg[u] += 1
dfs(0, -1)
for (a, b) in ans:
	print(a + 1, b + 1)


from heapq import heappush, heappop
(N, M) = map(int, input().split())
(A, B) = zip(*(map(int, input().split()) for _ in range(M))) if M else ((), ())

class UnionFindTree:

	def __init__(self, n):
		self.p = [i for i in range(n + 1)]
		self.r = [1 for _ in range(n + 1)]

	def find(self, x):
		if self.p[x] != x:
			self.p[x] = self.find(self.p[x])
		return self.p[x]

	def union(self, x, y):
		px = self.find(x)
		py = self.find(y)
		if self.r[px] < self.r[py]:
			self.r[py] += self.r[px]
			self.p[px] = py
		else:
			self.r[px] += self.r[py]
			self.p[py] = px

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return self.r[self.find(x)]
utf = UnionFindTree(N)
T = [{} for _ in range(N + 1)]
for (a, b) in zip(A, B):
	if not utf.same(a, b):
		T[a][b] = 1
		T[b][a] = 1
		utf.union(a, b)
INF = 10 ** 9

def dijkstra(G, s):
	dp = [INF for _ in range(len(G))]
	q = []
	heappush(q, (0, s))
	while q:
		(c, i) = heappop(q)
		if dp[i] == INF:
			dp[i] = c
			for (j, w) in G[i].items():
				heappush(q, (c + w, j))
	return dp
r = dijkstra(T, 1)
p = [0, 1] + [min(T[i], key=lambda j: r[j]) for i in range(2, N + 1)]
dp = [0 for _ in range(N + 1)]
for (a, b) in zip(A, B):
	if b not in T[a]:
		dp[a] += 1
for i in sorted(range(1, N + 1), key=lambda j: r[j], reverse=True):
	dp[i] += sum(((dp[j] + 1) % 2 for j in T[i] if j != p[i]))
ans = -1 if M % 2 == 1 else '\n'.join(('{} {}'.format(a, b) if b not in T[a] or (dp[a] % 2 == 1 and p[a] == b or (dp[b] % 2 == 0 and p[b] == a)) else '{} {}'.format(b, a) for (a, b) in zip(A, B)))
print(ans)


import sys
sys.setrecursionlimit(1000000)
(n, m) = [int(x) for x in input().split()]
edges = []
g = [[] for _ in range(n)]
for _ in range(m):
	(a, b) = [int(x) for x in input().split()]
	a -= 1
	b -= 1
	e = len(edges)
	g[a].append(e)
	g[b].append(e)
	edges.append((a, b))
if m % 2 == 1:
	print(-1)
	sys.exit(0)
visited = [False] * n
visitede = [False] * m

def build_stree(i):
	cts = []
	for e in g[i]:
		j = edges[e][1 if edges[e][0] == i else 0]
		if visited[j]:
			continue
		visitede[e] = True
		visited[j] = True
		cts.append((e, build_stree(j)))
	return (i, cts)
visited[0] = True
st = build_stree(0)
rev_e = [None if v else False for v in visitede]

def pos(t):
	(i, cts) = t
	for (_, ct) in cts:
		pos(ct)
	es = [e for e in g[i] if rev_e[e] is None]
	assert len(es) <= 1
	if not es:
		return
	f = es[0]
	rev_e[f] = (sum(((edges[e][0] == i) ^ rev_e[e] for e in g[i] if e != f)) % 2 != 0) ^ (edges[f][0] == i)
pos(st)
for (ed, re) in zip(edges, rev_e):
	if re:
		(b, a) = ed
	else:
		(a, b) = ed
	print(a + 1, b + 1)


import sys
sys.setrecursionlimit(10 ** 6)
(N, M) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
if M % 2 == 1:
	print(-1)
	sys.exit()

class UnionFind:

	def __init__(self, size):
		self.table = [-1 for i in range(size + 1)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			return self.find(self.table[x])

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return False
		if self.table[s1] < self.table[s2]:
			self.table[s1] = self.table[s1] + self.table[s2]
			self.table[s2] = self.find(x)
		else:
			self.table[s2] = self.table[s1] + self.table[s2]
			self.table[s1] = self.find(y)
		return True
UF = UnionFind(N)
ans = []
T = [[-1] for i in range(N + 1)]
color = [-1 for i in range(N + 1)]
counta = [0 for i in range(N + 1)]
B = []
C = [[] for i in range(N + 1)]
for c in A:
	if UF.union(c[0], c[1]):
		B.append(c)
		C[c[0]].append(c[1])
		C[c[1]].append(c[0])
	else:
		ans.append(c)
		counta[c[0]] += 1

def b(x):
	color[x] = 1
	for c in C[x]:
		if color[c] == -1:
			T[c][0] = x
			T[x].append(c)
			b(c)
b(1)
edge_leaf = []
for i in range(1, N + 1):
	if len(T[i]) == 1:
		edge_leaf.append(i)

def a(x):
	p = T[x][0]
	if p == -1:
		return 0
	if counta[x] % 2 == 0:
		ans.append([p, x])
		counta[p] += 1
	else:
		ans.append([x, p])
	return p
for c in edge_leaf:
	point = c
	while color[point] == len(T[point]):
		point = a(point)
		color[point] += 1
for c in ans:
	print(' '.join(map(str, c)))


def solve():
	(N, M) = map(int, input().split())
	if M % 2:
		return '-1'
	E = [set() for _ in range(N + 1)]
	for _ in range(M):
		(a, b) = map(int, input().split())
		E[a].add(b)
		E[b].add(a)
	q = [(0, 1, 1)]
	v = set()
	T = []
	while q:
		(n_, n, d) = q.pop()
		if n not in v:
			T.append((d, n_, n))
			E[n].discard(n_)
			E[n_].discard(n)
			v.add(n)
			if E[n] - v:
				q.extend([(n, u, d + 1) for u in E[n] - v])
	A = [0 for _ in range(N + 1)]
	res = []
	c = set()
	for (d, a, b) in sorted(T, reverse=1)[:-1]:
		F = E[b] - c
		if A[b] % 2 == 0 or len(E[b]) % 2:
			res.extend([(u, b) for u in F])
			for u in F:
				A[u] += 1
				E[u] -= {b}
		else:
			res.extend([(b, u) for u in F])
			for u in F:
				A[b] += 1
				E[u] -= {b}
		E[a] -= {b}
		if A[b] % 2:
			A[b] += 1
			res.extend([(b, a)])
		else:
			A[a] += 1
			res.extend([(a, b)])
	return '\n'.join(['{} {}'.format(*e) for e in res])
print(solve())


class Uf:

	def __init__(self, N):
		self.p = list(range(N))
		self.rank = [0] * N
		self.size = [1] * N

	def root(self, x):
		if self.p[x] != x:
			self.p[x] = self.root(self.p[x])
		return self.p[x]

	def same(self, x, y):
		return self.root(x) == self.root(y)

	def unite(self, x, y):
		u = self.root(x)
		v = self.root(y)
		if u == v:
			return
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
			self.size[v] += self.size[u]
			self.size[u] = 0
		else:
			self.p[v] = u
			self.size[u] += self.size[v]
			self.size[v] = 0
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1

	def count(self, x):
		return self.size[self.root(x)]
(N, M) = map(int, input().split())
if M % 2 == 1:
	print(-1)
	exit()
E = [set() for _ in range(N + 1)]
E_mst = [set() for _ in range(N + 1)]
uf = Uf(N + 1)
for _ in range(M):
	(a, b) = map(int, input().split())
	E[a].add(b)
	E[b].add(a)
	if not uf.same(a, b):
		E_mst[a].add(b)
		E_mst[b].add(a)
		uf.unite(a, b)
Cnt = [len(e) for e in E_mst]
q = {i for (i, c) in enumerate(Cnt) if c == 1}
Used = set()
Ans = []
while q:
	v = q.pop()
	if len(E_mst[v]) == 1:
		vp = E_mst[v].pop()
	else:
		vp = -1
	l = len(E[v])
	for u in E[v].copy():
		if u != vp:
			(v_, u_) = (v, u) if v < u else (u, v)
			if (v_, u_) not in Used:
				Ans.append((v, u))
				E[u].remove(v)
				E[v].remove(u)
				Used.add((v_, u_))
	if l % 2 == 0:
		try:
			E[vp].remove(v)
			E[v].remove(vp)
		except:
			break
		Ans.append((v, vp))
		Used.add((v, vp) if v < vp else (vp, v))
	E_mst[vp].remove(v)
	if len(E_mst[vp]) == 1:
		q.add(vp)
if len(Ans) != M:
	print(Ans)
	print(-1)
	assert False
	exit()
for a in Ans:
	print(' '.join(map(str, a)))


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
X = [[] for i in range(N)]
k = 0
for i in range(M):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
	k += 1
if k % 2:
	print(-1)
else:
	ANS = []
	P = [-1] * N
	Q = [(-1, 0)]
	done = [0] * N
	C = [0] * N
	R = []
	while Q:
		(pre, i) = Q.pop()
		if done[i]:
			C[i] += 1
			if pre >= 0:
				ANS.append((i, pre))
			continue
		done[i] = 1
		R.append(i)
		for a in X[i]:
			if a != P[i]:
				P[a] = i
				X[a].remove(i)
				Q.append((i, a))
	for i in R[1:][::-1]:
		if C[i] % 2:
			ANS.append((i, P[i]))
		else:
			ANS.append((P[i], i))
			C[P[i]] += 1
	for (a, b) in ANS:
		print(a + 1, b + 1)


from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
(n, m) = map(int, input().split())
if m & 1:
	print(-1)
	exit()
g = [set() for _ in range(n + 1)]
for _ in range(m):
	(a, b) = map(int, input().split())
	g[a].add(b)
	g[b].add(a)
seen = [False] * (n + 1)
seen[1] = True
mst = [set() for _ in range(n + 1)]
dq = deque()
dq.append(1)
while dq:
	v = dq.popleft()
	for u in g[v]:
		if seen[u]:
			continue
		seen[u] = True
		mst[u].add(v)
		mst[v].add(u)
		dq.append(u)
ans = set()
deg = [0] * (n + 1)
for v in range(1, n + 1):
	for u in g[v]:
		if v > u:
			continue
		if u not in mst[v]:
			ans.add((u, v))
			deg[u] += 1

def dfs(v, pr):
	for u in mst[v]:
		if u == pr:
			continue
		dfs(u, v)
	if pr == -1:
		return
	if deg[v] % 2 == 0:
		ans.add((pr, v))
		deg[pr] += 1
	else:
		ans.add((v, pr))
		deg[v] += 1
dfs(1, -1)
for aa in ans:
	print(*aa)


import sys
input = sys.stdin.readline
from bisect import bisect_left
from collections import deque

def count_edge(a, b):
	global edge, AB
	if a > b:
		(a, b) = (b, a)
	edge[bisect_left(AB, (a, b))] += 1

def main():
	global edge, AB
	(N, M) = map(int, input().split())
	data = [[] for i in range(N + 1)]
	AB = []
	edge = [0] * M
	count = [0] * (N + 1)
	for i in range(M):
		(A, B) = map(int, input().split())
		if A > B:
			(A, B) = (B, A)
		AB.append((A, B))
		data[A].append(B)
		data[B].append(A)
		count[A] ^= 1
	AB.sort()
	if M % 2 == 1:
		print(-1)
		sys.exit()
	parent = [0] * (N + 1)
	que = [1]
	parent[1] = 1
	lsls = deque([])
	while que:
		h = []
		for u in que:
			for v in data[u]:
				if parent[v] == 0:
					parent[v] = u
					h.append(v)
					if count[v] % 2 == 1:
						lsls.appendleft(v)
		que = h
	for i in lsls:
		if count[i] == 0:
			continue
		else:
			count[i] = 0
			while True:
				j = parent[i]
				if i == j:
					break
				count_edge(i, j)
				if count[j] == 1:
					count[j] = 0
					break
				i = j
	for i in range(M):
		if edge[i] % 2 == 0:
			print(*AB[i])
		else:
			print(*AB[i][::-1])
main()


import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)

def solve(n, m, links):
	if m % 2 == 1:
		print(-1)
		return
	tree = [set() for _ in range(n)]
	parents = [-1] * n
	q = deque([0])
	while q:
		v = q.popleft()
		for u in links[v]:
			if parents[u] == -1:
				tree[v].add(u)
				parents[u] = v
				q.append(u)
			links[u].remove(v)
	parities = [len(l) % 2 for l in links]

	def dfs(v):
		b = parities[v]
		for u in tree[v]:
			c = dfs(u)
			b ^= c
		if b:
			p = parents[v]
			links[p].remove(v)
			links[v].add(p)
		return b
	dfs(0)
	ans = ['{} {}'.format(v + 1, u + 1) for v in range(n) for u in links[v]]
	print('\n'.join(ans))
(n, m) = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
	(a, b) = map(int, line.split())
	a -= 1
	b -= 1
	links[a].add(b)
	links[b].add(a)
solve(n, m, links)


(n, m) = map(int, input().split())
g = {}
ori = []
for _ in range(m):
	(u, v) = map(int, input().split())
	ori.append((u, v))
	if u not in g:
		g[u] = []
	g[u].append(v)
	if v not in g:
		g[v] = []
	g[v].append(u)

def solve(g, ori):
	p = {}
	p[1] = 1
	i = 0
	S = [1]
	used = [False] * (n + 1)
	cnt = [0] * (n + 1)
	edge = []
	used[1] = True
	while i < len(S):
		cur = S[i]
		for u in g[cur]:
			if used[u] == True:
				continue
			used[u] = True
			p[u] = cur
			S.append(u)
		i += 1
	for (u, v) in ori:
		if p[u] != v and p[v] != u:
			cnt[u] += 1
			edge.append((u, v))
	for u in S[::-1][:-1]:
		if cnt[u] % 2 == 0:
			edge.append((p[u], u))
			cnt[p[u]] += 1
		else:
			edge.append((u, p[u]))
	return edge
s = ''
if m % 2 == 1:
	print('-1')
else:
	edge = solve(g, ori)
	for (x, y) in edge:
		s += str(x) + ' ' + str(y) + '\n'
	print(s)


from collections import deque
(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
if m % 2:
	print(-1)
	exit()
adj = [[] for _ in range(n + 1)]
for (a, b) in ab:
	adj[a].append(b)
	adj[b].append(a)
s = 1
dq = deque([s])
d = [-1] * (n + 1)
d[s] = 0
p = [-1] * (n + 1)
order = []
while dq:
	u = dq.popleft()
	order.append(u)
	for v in adj[u]:
		if d[v] == -1:
			d[v] = d[u] + 1
			p[v] = u
			dq.append(v)
out = [0] * (n + 1)
ans = []
for (a, b) in ab:
	if p[a] == b or p[b] == a:
		continue
	ans.append((a, b))
	out[a] ^= 1
for v in order[1:][::-1]:
	u = p[v]
	if out[v]:
		ans.append((v, u))
		out[v] ^= 1
	else:
		ans.append((u, v))
		out[u] ^= 1
for (u, v) in ans:
	print(u, v)


from collections import deque

class UnionFind:

	def __init__(self, n):
		self.parent = [-1] * n
		self.cnt = n

	def root(self, x):
		if self.parent[x] < 0:
			return x
		else:
			self.parent[x] = self.root(self.parent[x])
			return self.parent[x]

	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		if self.parent[x] > self.parent[y]:
			(x, y) = (y, x)
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		self.cnt -= 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def get_size(self, x):
		return -self.parent[self.root(x)]
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
if m % 2 == 1:
	print(-1)
	exit()
uf = UnionFind(n)
tree = [[] for i in range(n)]
out_deg = [0] * n
ans = []
for (u, v) in info:
	(u, v) = (u - 1, v - 1)
	if uf.is_same(u, v):
		ans.append((u + 1, v + 1))
		out_deg[u] += 1
	else:
		uf.merge(u, v)
		tree[u].append(v)
		tree[v].append(u)
root = 0
q = deque([root])
par = {0: -1}
topo = []
while q:
	v = q.popleft()
	topo.append(v)
	for nxt_v in tree[v]:
		if nxt_v in par:
			continue
		par[nxt_v] = v
		q.append(nxt_v)
while topo:
	v = topo.pop()
	if v == 0:
		break
	if out_deg[v] % 2 == 1:
		out_deg[v] += 1
		ans.append((v + 1, par[v] + 1))
	else:
		out_deg[par[v]] += 1
		ans.append((par[v] + 1, v + 1))
for res in ans:
	print(*res)


from collections import deque

def bfs():
	q = deque()
	q.append(1)
	dist[1] = 0
	while q:
		i = q.popleft()
		for g in G[i]:
			(j, x) = (g[0], g[1])
			if dist[j] == -1:
				dist[j] = dist[i] + 1
				q.append(j)
				euse[x] = 1
				T[i].append([j, x])
				T[j].append([i, x])
				parent[j] = i
				v.append(j)
	return
(n, m) = map(int, input().split())
G = [[] for _ in range(n + 1)]
E = []
for i in range(m):
	(a, b) = map(int, input().split())
	G[a].append([b, i])
	G[b].append([a, i])
	E.append([a, b])
if m % 2 == 1:
	print(-1)
	exit()
T = [[] for _ in range(n + 1)]
euse = [0] * m
dist = [-1] * (n + 1)
parent = [0] * (n + 1)
v = deque()
bfs()
start = [0] * (n + 1)
for i in range(m):
	if not euse[i]:
		print(E[i][0], E[i][1])
		start[E[i][0]] += 1
while v:
	i = v.pop()
	for t in T[i]:
		if parent[i] == t[0]:
			(j, x) = (t[0], t[1])
			break
	if start[i] % 2 == 0:
		start[j] += 1
		print(j, i)
	else:
		start[i] += 1
		print(i, j)


import sys
sys.setrecursionlimit(10 ** 9)
(N, M) = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(M):
	(A, B) = map(int, input().split())
	adjL[A - 1].append(B - 1)
	adjL[B - 1].append(A - 1)
if M % 2:
	print(-1)
	sys.exit()

def makeSpanningTree(vNow, vPar):
	useds[vNow] = True
	for v2 in adjL[vNow]:
		if v2 == vPar:
			pass
		elif useds[v2]:
			if vNow < v2:
				anss.append((vNow, v2))
				outdegs[vNow] += 1
		else:
			adjL2[vNow].append(v2)
			adjL2[v2].append(vNow)
			makeSpanningTree(v2, vNow)
anss = []
adjL2 = [[] for _ in range(N)]
outdegs = [0] * N
useds = [False] * N
makeSpanningTree(0, -1)

def dfs(vNow, vPar):
	for v2 in adjL2[vNow]:
		if v2 != vPar:
			dfs(v2, vNow)
	if outdegs[vNow] % 2:
		anss.append((vNow, vPar))
		outdegs[vNow] += 1
	else:
		anss.append((vPar, vNow))
		outdegs[vPar] += 1
dfs(0, -1)
anss.pop()
print('\n'.join(map(lambda x: str(x[0] + 1) + ' ' + str(x[1] + 1), anss)))


import sys
from collections import defaultdict, deque
import heapq

def solve(N: int, M: int, A: 'List[int]', B: 'List[int]'):
	if M % 2 != 0:
		print(-1)
		return
	adj = defaultdict(set)
	for (a, b) in zip(A, B):
		adj[a].add(b)
		adj[b].add(a)
	parent = [None for _ in range(N)]
	children = [set() for _ in range(N)]
	res = set()
	count = [0 for _ in range(N)]
	Q = deque([0], N)
	visited = [False for _ in range(N)]
	visited[0] = True
	while len(Q) > 0:
		u = Q.popleft()
		for v in adj[u]:
			if parent[u] == v:
				continue
			if visited[v]:
				if (v, u) in res:
					continue
				res.add((u, v))
				count[u] += 1
				continue
			parent[v] = u
			children[u].add(v)
			visited[v] = True
			Q.append(v)
	visited = [False for _ in range(N)]
	Q = deque([0], N)
	while len(Q) > 0:
		u = Q.popleft()
		if len(children[u]) > 0 and (not all((visited[v] for v in children[u]))):
			Q.appendleft(u)
			Q.extendleft(children[u])
			continue
		if parent[u] is None:
			visited[u] = True
			continue
		v = parent[u]
		if count[u] % 2 == 0:
			res.add((v, u))
			count[v] += 1
		else:
			res.add((u, v))
			count[u] += 1
		visited[u] = True
	for (c, d) in res:
		print(c + 1, d + 1)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	M = int(next(tokens))
	A = [int()] * M
	B = [int()] * M
	for i in range(M):
		A[i] = int(next(tokens)) - 1
		B[i] = int(next(tokens)) - 1
	solve(N, M, A, B)
main()


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return sys.stdin.readline().rstrip()

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def main():
	(n, m) = LI()
	if m % 2 == 1:
		print(-1)
		exit()
	graph = defaultdict(set)
	grapht = defaultdict(set)
	for i in range(m):
		(a, b) = LI()
		a -= 1
		b -= 1
		graph[a].add(b)
		graph[b].add(a)
		grapht[a].add(b)
		grapht[b].add(a)
	graph2 = defaultdict(set)
	visited = [0 for i in range(n)]
	num = [1 for i in range(n)]

	def dfs(x):
		visited[x] = 1
		for nx in graph[x]:
			if not visited[nx]:
				dfs(nx)
		t = set()
		if num[x] == 1 and len(grapht[x]) % 2 == 0:
			for e in grapht[x]:
				graph2[x].add(e)
				t.add(e)
		elif num[x] == -1 and len(grapht[x]) % 2 == 0:
			for (j, e) in enumerate(grapht[x]):
				if j == len(grapht[x]) - 1:
					graph2[e].add(x)
					num[e] *= -1
				else:
					graph2[x].add(e)
				t.add(e)
		elif num[x] == 1 and len(grapht[x]) % 2 == 1:
			for (j, e) in enumerate(grapht[x]):
				if j == len(grapht[x]) - 1:
					graph2[e].add(x)
					num[e] *= -1
				else:
					graph2[x].add(e)
				t.add(e)
		elif num[x] == -1 and len(grapht[x]) % 2 == 1:
			for e in grapht[x]:
				graph2[x].add(e)
				t.add(e)
		for e in t:
			grapht[x].remove(e)
			grapht[e].remove(x)
	dfs(0)
	for i in range(n):
		for e in graph2[i]:
			print(i + 1, e + 1)
main()