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

Solution (Python):

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)

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


if __name__ == '__main__':
    main()

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

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

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

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

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

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

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

Solution (Python):
from collections import deque


class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素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を含む集合と要素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):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """要素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)

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

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

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

Solution (Python):
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 (min(v, nv), max(v, nv)) not in used:
            used.add((min(v, nv), max(v, nv)))
            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)

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


tree = [[] for _ in range(n)]
lev = [0] * n
vis = [False] * n
vis[0] = True
reserve = set()
q = [0]
while q:
	cur = q.pop()
	for nxt in con[cur]:
		if vis[nxt]:
			continue
		reserve.add((cur, nxt))
		tree[cur] += nxt,
		tree[nxt] += cur,
		lev[cur] += 1
		lev[nxt] += 1
		vis[nxt] = True
		q += nxt,


ans = []
deg = [0] * n
for s, t in zip(*[iter(L)] * 2):
	if (s - 1, t - 1) not in reserve and (t - 1, s - 1) not in reserve:
		ans += "{} {}".format(s, t),
		deg[s - 1] ^= 1


from collections import deque
q = deque()
done = [False] * n
for i, l in enumerate(lev):
	if l == 1:
		q.append(i)
while q:
	cur = q.popleft()
	for nxt in tree[cur]:
		if done[nxt]:
			continue
		if deg[cur]:
			ans += "{} {}".format(cur + 1, nxt + 1),
			deg[cur] ^= 1
		else:
			ans += "{} {}".format(nxt + 1, cur + 1),
			deg[nxt] ^= 1
		done[cur] = True
		lev[nxt] -= 1
		if lev[nxt] == 1:
			q.append(nxt)

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

Solution (Python):

"""
無理な場合を考えてみよう
→全体の辺の本数が奇数なら絶対無理

それ以外は？
説1:辺が偶数なら絶対作れる説

辺を選択し、そのどちらか片方にのみ xor1する
→すべての辺の数字を0にできるか？？(初期値は0)
なんかできそう

辺の向きを変えることで1を伝播させることが出来る
→同じ点にぶつけられる！！
ので、偶数本なら絶対できる


どうやって構成する？
適当に置く→1の点を適当に2つ選び、パス上にある辺を全部反転させる
確かにできるけど…遅くね？

もっと簡単にできないか？
適当に木を取る→深い方から整合性を合わせていけば終わり(最終的には根に収束するので)
各点に関して動かすのは高々1辺だけだから、木を取った辺のみ考えて反転させる
(それ以外は適当に置いておく)

dfsで終わり→解けた！！！
"""
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)

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

Solution (Python):
from collections import deque


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

    def root(self, x):
        """頂点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を含む集合と頂点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):
        """頂点xと頂点yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """頂点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)

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

        

if __name__ == "__main__":
    main()

Solution (Python):
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
    AB[a*(10**5+1)+b]^=1
def main():
    global edge,AB
    N,M=map(int,input().split())
    data=[[] for i in range(N+1)]
    AB={}
    count=[0]*(N+1)
    for i in range(M):
        A,B=map(int,input().split())
        if A>B:
            A,B=B,A
        AB[A*(10**5+1)+B]=0
        data[A].append(B)
        data[B].append(A)
        count[A]^=1

    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
    num=10**5+1
    for u,j in zip(AB.keys(),AB.values()):
        if j!=1:
            print(u//num,u%num)
        else:
            print(u%num,u//num)
if __name__=="__main__":
    main()

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