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


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
            

"""
幅優先探索で葉から辿ったところ、
すべての子を考慮する前にpのdegreeが決まってしまっている。
深さ優先探索に修正
"""
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)

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

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

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

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

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

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

Solution (Python):
import sys
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([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([u+1, v+1])
            degree[u] += 1
        else:
            ans.append([v+1, u+1])
            degree[v] += 1

dfs()

if degree[0] % 2 == 1:
    print(-1)
else:
    for pair in ans:
        print(' '.join(map(str, pair)))

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

Solution (Python):
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 + 1)]
for a, b in AB:
    repn[a].append(b)
    repn[b].append(a)



tree = [set() for i in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
q = deque([1])

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 + 1)
ans = []

for a, b in AB:
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a, b))
    degree[a] += 1



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

dfs()

if degree[1] % 2 == 1:
    print(-1)
else:
    print('\n'.join(ans))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

n, m = map(int, input().split())

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



AB = [[int(x) for x in input().split()] for _ in range(m)]


repn = [[] for j in range(n + 1)]
for a, b in AB:
    repn[a].append(b)
    repn[b].append(a)



tree = [set() for i in range(n + 1)]
visited = [False] * (n + 1)
visited[1] = True
q = deque([1])

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 + 1)
ans = []

for a, b in AB:
    if b in tree[a]:
        continue
    ans.append('{} {}'.format(a, b))
    degree[a] += 1



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

dfs()

print('\n'.join(ans))

Solution (Python):



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)

Solution (Python):

"""
Created on Thu Jul 18 12:05:59 2019

@author: ctiuser
"""
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)))

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

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
eff = [0 for _ in range(n)]
edges = []
visited = [False for _ in range(n)]
is_reversed = [0 for _ in range(m)]

for i in range(m):
	a, b = map(int, input().split())
	adj[a-1].append([b-1, i])
	adj[b-1].append([a-1, i])
	edges.append([a, b])
	eff[a-1] ^= 1

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

def dfs(x, e):
	for v, i in adj[x]:
		if not visited[v]:
			visited[v] = True
			dfs(v, i)
	if e == -1:
		return
	else:
		if eff[x] == 1:
			is_reversed[e] ^= 1
			eff[x] ^= 1
			eff[(edges[e][0]-1) * (edges[e][1]-1) // x] ^= 1
		return

visited[0] = True
dfs(0, -1)
for i in range(m):
	if is_reversed[i]:
		print(*edges[i][::-1])
	else:
		print(*edges[i])

Solution (Python):

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


if __name__ == '__main__':
    B()

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

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

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

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

if __name__ == '__main__':
  main()

Solution (Python):
def b_even_degrees(N, M, Edges):
    """
    N頂点M辺の単純連結無向グラフが与えられる。
    それのすべての辺に向きをつけ、任意の頂点から出る辺の本数も偶数となるような
    有向グラフを作れるか判定し、可能なら1つ構成せよ。

    すべての辺はどこかの頂点から出なければならないので、辺の数が奇数だと作れない。
    偶数の場合は必ず構成できる。
    ・適当な根付き全域木を取り、残りの辺を適当に向き付ける
    ・木の頂点vとその親を結ぶ辺の向きを決めるときは、vの出次数が偶数になるようにする
    これで、根以外の出次数は偶数になっており、根の出次数は、全体の出次数の
    和が偶数であることから偶数である。
    """
    
    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))

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