Problem:
 Score : 700 points    Problem Statement 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.      Notes An undirected graph is said to be simple when it contains no self-loops or multiple edges.      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.        Sample Input 1 4 4
1 2
2 3
3 4
4 1      Sample Output 1 1 2
1 4
3 2
3 4  After this assignment of directions, Vertex 1 and 3 will each have two outgoing edges, and Vertex 2 and 4 will each have zero outgoing edges.       Sample Input 2 5 5
1 2
2 3
3 4
2 5
4 5      Sample Output 2 -1

Solution (Python):
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 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")

Solution (Python):
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")

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
from heapq import *
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for id in range(M):
    a, b = map(int, input().split())
    es[a].append([b, id])
    es[b].append([a, id])
edge = [None] * M
h = [0] * (N+1)
lev = [None] * (N+1)
visit = [0] * (N+1)
def dfs(v, d):
    if visit[v]: return
    lev[v] = d
    visit[v] = 1
    for u, id in es[v]:
        if edge[id] == None:
            edge[id] = [v, u]
            h[v] ^= 1
            dfs(u, d+1)
dfs(1, 0)
q = [(-lev[v], v) for v in range(1, N+1)]
heapify(q)
while q:
    lv, v = heappop(q)
    lv = -lv
    if h[v] % 2 == 0: continue
    for u, id in es[v]:
        if lev[u] < lv:
            h[v] ^= 1
            h[u] ^= 1
            k, l = edge[id]
            edge[id] = [l, k]
            break
if h[1]:
    print(-1)
else:
    for u, v in edge:
        print(u, v)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):

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])


if __name__ == '__main__':
    print(solve())

Solution (Python):
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])

Solution (Python):

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)

if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):


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)

Solution (Python):
from collections import defaultdict
import sys

def dfs(visited, graph, grapht, graph2, num, x):
  visited[x] = 1

  for nx in graph[x]:
    if not visited[nx]:
      dfs(visited, graph, grapht, graph2, num, 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]) and len(grapht[x])%2==0:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  elif num[x]==1 and len(grapht[x])%2==1:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
    tt = grapht[x].pop()
    graph2[tt].add(x)
    graph2[x].remove(tt)
    num[tt] *= -1
  else:
    for e in grapht[x]:
      graph2[x].add(e)
      t.add(e)
  for e in t:
    if e in grapht[x]:
      grapht[x].remove(e)
    if x in grapht[e]:
      grapht[e].remove(x)

if __name__ == "__main__":
  sys.setrecursionlimit(1000000)
  input = sys.stdin.readline
  n, m = map(int, input().split())

  if m%2==1:
    print(-1)
    exit()

  graph = defaultdict(set)
  grapht = defaultdict(set)
  for i in range(m):
    a, b = 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]*n
  num = [1]*n

  dfs(visited, graph, grapht, graph2, num, 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)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

n, m = map(int,input().split())
A = [[int(i) for i in input().split()] for i in range(m)]

if m&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)

Solution (Python):
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)))

Solution (Python):
import numpy as np
from collections import deque
import heapq




N, M = map(int, input().split())

edges = [set() for _ in range(N)]
degs = [0 for i in range(N)]
parity = [0 for _ in range(N)]
flag = [False for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
    degs[a-1] += 1
    degs[b-1] += 1

if M%2 != 0:
    print(-1)
    exit()



Q = []

for i, d in enumerate(degs):
    Q.append((d,i))
heapq.heapify(Q)

while len(Q) > 0:
    _, u = Q[0]
    heapq.heappop(Q)
    if flag[u]:
        continue
    flag[u] = True

    for i, v in enumerate(edges[u]):
        edges[v].remove(u)
        if parity[u] != 0 and i == 0:
            print(u+1, v+1)
            parity[u] = 1 - parity[u]
        else:
            print(v+1, u+1)
            parity[v] = 1 - parity[v]


        degs[v] -= 1
        heapq.heappush(Q, (degs[v], v))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))