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):
from collections import defaultdict
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):
  for e in graph2[i]:
    print(i+1, e+1)

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

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

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

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

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

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

Solution (Python):

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

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

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


if __name__ == '__main__':
    main()

Solution (Python):


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)

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

Solution (Python):

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


if __name__ == "__main__":
    B()

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

Solution (Python):
if __name__ == '__main__':
    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)

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

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

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

    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:
                nxt.node.parent = nxt.another()
                s.append(nxt.node)

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

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

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

Solution (Python):
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 = [(0, nodes[1])]
idx = 0
while len(s) > 0:
    level, cur = s.pop()

    nxtlevel = level + 1
    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:
                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.bridge.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):
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)