Buggy python submission (verdict: Time Limit Exceeded):
import sys
import random
from collections import deque

input = sys.stdin.buffer.readline

class LCA:
    "0-indexed"

    def __init__(self, adj, root = 0):  
        N = len(adj) 
        parent = [-1] * N
        self.depth = [0] * N
        q = deque([root])
        while q:
            node = q.popleft()
            for next_node in adj[node]:
                if parent[node] != next_node:
                    parent[next_node] = node
                    q.append(next_node)
                    self.depth[next_node] = self.depth[node] + 1
                        
        self.ancestor = [parent] #self.ancestor[k][u]はuの2**k先の祖先。
        k = 1
        while (1 << k) < N:
            anc_k = [0] * N
            for u in range(N):
                if self.ancestor[-1][u] == -1:
                    anc_k[u] = -1
                else:
                    anc_k[u] = self.ancestor[-1][self.ancestor[-1][u]]
            self.ancestor.append(anc_k)
            k += 1

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        for k, bit in enumerate(reversed(format(self.depth[u]-self.depth[v], 'b'))):
            if bit == '1':
                u = self.ancestor[k][u]
        if u == v:
            return u
        for anc in reversed(self.ancestor):
            if anc[u] != anc[v]:
                u = anc[u]
                v = anc[v]
        return self.ancestor[0][u]



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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])

# 気合で木にする。（LCAを使いたいから。）
root = random.randint(1, N)
q = [root]
pseudo_parent = [0] * (N+1)
pseudo_parent[root] = root
pseudo_adj = [[] for _ in range(N)] #This is 0-indexed.
while q:
    nq = []
    for v in q:
        for nv in inv_ABs[v]:
            if pseudo_parent[nv] == 0:
                pseudo_parent[nv] = v
                pseudo_adj[v-1].append(nv-1)
                pseudo_adj[nv-1].append(v-1)
                nq.append(nv)
    q = nq

lca = LCA(pseudo_adj, root-1)

odd_nodes = set((i for i, e in enumerate(iseven) if not e))
while odd_nodes:
    u = odd_nodes.pop()
    v = odd_nodes.pop()
    a = lca.lca(u-1, v-1) + 1
    while u != a:
        p = pseudo_parent[u]
        reverse_ABs[inv_ABs[u][p]] = (not reverse_ABs[inv_ABs[u][p]])
        u = p
    while v != a:
        p = pseudo_parent[v]
        reverse_ABs[inv_ABs[v][p]] = (not reverse_ABs[inv_ABs[v][p]])
        v = p    
    # assert len(odd_nodes) % 2 == 0

for rflg, (A, B) in zip(reverse_ABs, ABs):
    if rflg:
        print(B, A)
    else:
        print(A, B)

Fixed submission:
# Euler Tourとimos法で殴る。
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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])


# Euler Tour
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])

# print(et)

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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import random
from collections import deque

input = sys.stdin.buffer.readline

class LCA:
    "0-indexed"

    def __init__(self, adj, root = 0):  
        N = len(adj) 
        parent = [-1] * N
        self.depth = [0] * N
        q = deque([root])
        while q:
            node = q.popleft()
            for next_node in adj[node]:
                if parent[node] != next_node:
                    parent[next_node] = node
                    q.append(next_node)
                    self.depth[next_node] = self.depth[node] + 1
                        
        self.ancestor = [parent] #self.ancestor[k][u]はuの2**k先の祖先。
        k = 1
        while (1 << k) < N:
            anc_k = [0] * N
            for u in range(N):
                if self.ancestor[-1][u] == -1:
                    anc_k[u] = -1
                else:
                    anc_k[u] = self.ancestor[-1][self.ancestor[-1][u]]
            self.ancestor.append(anc_k)
            k += 1

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        for k, bit in enumerate(reversed(format(self.depth[u]-self.depth[v], 'b'))):
            if bit == '1':
                u = self.ancestor[k][u]
        if u == v:
            return u
        for anc in reversed(self.ancestor):
            if anc[u] != anc[v]:
                u = anc[u]
                v = anc[v]
        return self.ancestor[0][u]



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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])

# 気合で木にする。（LCAを使いたいから。）
root = random.randint(1, N)
q = [root]
pseudo_parent = [0] * (N+1)
pseudo_parent[root] = root
pseudo_adj = [[] for _ in range(N)] #This is 0-indexed.
while q:
    nq = []
    for v in q:
        for nv in inv_ABs[v]:
            if pseudo_parent[nv] == 0:
                pseudo_parent[nv] = v
                pseudo_adj[v-1].append(nv-1)
                pseudo_adj[nv-1].append(v-1)
                nq.append(nv)
    q = nq

lca = LCA(pseudo_adj, root-1)

odd_nodes = set((i for i, e in enumerate(iseven) if not e))
while odd_nodes:
    u = odd_nodes.pop()
    v = odd_nodes.pop()
    a = lca.lca(u-1, v-1) + 1
    while u != a:
        p = pseudo_parent[u]
        reverse_ABs[inv_ABs[u][p]] = (not reverse_ABs[inv_ABs[u][p]])
        u = p
    while v != a:
        p = pseudo_parent[v]
        reverse_ABs[inv_ABs[v][p]] = (not reverse_ABs[inv_ABs[v][p]])
        v = p    
    # assert len(odd_nodes) % 2 == 0

for rflg, (A, B) in zip(reverse_ABs, ABs):
    if rflg:
        print(B, A)
    else:
        print(A, B)

Fixed submission:
# Euler Tourとimos法で殴る。
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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])


# Euler Tour
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])

# print(et)

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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque
from random import shuffle

input = sys.stdin.buffer.readline

class LCA:
    "0-indexed"

    def __init__(self, adj):  
        N = len(adj) 
        parent = [-1] * N
        self.depth = [0] * N
        q = deque([0])
        while q:
            node = q.popleft()
            for next_node in adj[node]:
                if parent[node] != next_node:
                    parent[next_node] = node
                    q.append(next_node)
                    self.depth[next_node] = self.depth[node] + 1
                        
        self.ancestor = [parent] #self.ancestor[k][u]はuの2**k先の祖先。
        k = 1
        while (1 << k) < N:
            anc_k = [0] * N
            for u in range(N):
                if self.ancestor[-1][u] == -1:
                    anc_k[u] = -1
                else:
                    anc_k[u] = self.ancestor[-1][self.ancestor[-1][u]]
            self.ancestor.append(anc_k)
            k += 1

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        for k, bit in enumerate(reversed(format(self.depth[u]-self.depth[v], 'b'))):
            if bit == '1':
                u = self.ancestor[k][u]
        if u == v:
            return u
        for anc in reversed(self.ancestor):
            if anc[u] != anc[v]:
                u = anc[u]
                v = anc[v]
        return self.ancestor[0][u]



N, M = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(M)]
shuffle(ABs)

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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])

# 気合で木にする。（LCAを使いたいから。）
q = [1]
pseudo_parent = [0] * (N+1)
pseudo_parent[1] = 1
pseudo_adj = [[] for _ in range(N)] #This is 0-indexed.
while q:
    nq = []
    for v in q:
        for nv in inv_ABs[v]:
            if pseudo_parent[nv] == 0:
                pseudo_parent[nv] = v
                pseudo_adj[v-1].append(nv-1)
                pseudo_adj[nv-1].append(v-1)
                nq.append(nv)
    q = nq

lca = LCA(pseudo_adj)

odd_nodes = set((i for i, e in enumerate(iseven) if not e))
while odd_nodes:
    u = odd_nodes.pop()
    v = odd_nodes.pop()
    a = lca.lca(u-1, v-1) + 1
    while u != a:
        p = pseudo_parent[u]
        reverse_ABs[inv_ABs[u][p]] = (not reverse_ABs[inv_ABs[u][p]])
        u = p
    while v != a:
        p = pseudo_parent[v]
        reverse_ABs[inv_ABs[v][p]] = (not reverse_ABs[inv_ABs[v][p]])
        v = p    
    # assert len(odd_nodes) % 2 == 0

for rflg, (A, B) in zip(reverse_ABs, ABs):
    if rflg:
        print(B, A)
    else:
        print(A, B)

Fixed submission:
# Euler Tourとimos法で殴る。
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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])


# Euler Tour
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])

# print(et)

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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

input = sys.stdin.buffer.readline

class LCA:
    "0-indexed"

    def __init__(self, adj):  
        N = len(adj) 
        parent = [-1] * N
        self.depth = [0] * N
        q = deque([0])
        while q:
            node = q.popleft()
            for next_node in adj[node]:
                if parent[node] != next_node:
                    parent[next_node] = node
                    q.append(next_node)
                    self.depth[next_node] = self.depth[node] + 1
                        
        self.ancestor = [parent] #self.ancestor[k][u]はuの2**k先の祖先。
        k = 1
        while (1 << k) < N:
            anc_k = [0] * N
            for u in range(N):
                if self.ancestor[-1][u] == -1:
                    anc_k[u] = -1
                else:
                    anc_k[u] = self.ancestor[-1][self.ancestor[-1][u]]
            self.ancestor.append(anc_k)
            k += 1

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        for k, bit in enumerate(reversed(format(self.depth[u]-self.depth[v], 'b'))):
            if bit == '1':
                u = self.ancestor[k][u]
        if u == v:
            return u
        for anc in reversed(self.ancestor):
            if anc[u] != anc[v]:
                u = anc[u]
                v = anc[v]
        return self.ancestor[0][u]



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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])

# 気合で木にする。（LCAを使いたいから。）
q = [1]
pseudo_parent = [0] * (N+1)
pseudo_parent[1] = 1
pseudo_adj = [[] for _ in range(N)] #This is 0-indexed.
while q:
    nq = []
    for v in q:
        for nv in inv_ABs[v]:
            if pseudo_parent[nv] == 0:
                pseudo_parent[nv] = v
                pseudo_adj[v-1].append(nv-1)
                pseudo_adj[nv-1].append(v-1)
                nq.append(nv)
    q = nq

lca = LCA(pseudo_adj)

odd_nodes = set((i for i, e in enumerate(iseven) if not e))
while odd_nodes:
    u = odd_nodes.pop()
    v = odd_nodes.pop()
    a = lca.lca(u-1, v-1) + 1
    while u != a:
        p = pseudo_parent[u]
        reverse_ABs[inv_ABs[u][p]] = (not reverse_ABs[inv_ABs[u][p]])
        u = p
    while v != a:
        p = pseudo_parent[v]
        reverse_ABs[inv_ABs[v][p]] = (not reverse_ABs[inv_ABs[v][p]])
        v = p    
    assert len(odd_nodes) % 2 == 0

for rflg, (A, B) in zip(reverse_ABs, ABs):
    if rflg:
        print(B, A)
    else:
        print(A, B)

Fixed submission:
# Euler Tourとimos法で殴る。
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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])


# Euler Tour
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])

# print(et)

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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

input = sys.stdin.buffer.readline

class LCA:
    "0-indexed"

    def __init__(self, adj):  
        N = len(adj) 
        parent = [-1] * N
        self.depth = [0] * N
        q = deque([0])
        while q:
            node = q.popleft()
            for next_node in adj[node]:
                if parent[node] != next_node:
                    parent[next_node] = node
                    q.append(next_node)
                    self.depth[next_node] = self.depth[node] + 1
                        
        self.ancestor = [parent] #self.ancestor[k][u]はuの2**k先の祖先。
        k = 1
        while (1 << k) < N:
            anc_k = [0] * N
            for u in range(N):
                if self.ancestor[-1][u] == -1:
                    anc_k[u] = -1
                else:
                    anc_k[u] = self.ancestor[-1][self.ancestor[-1][u]]
            self.ancestor.append(anc_k)
            k += 1

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        for k, bit in enumerate(reversed(format(self.depth[u]-self.depth[v], 'b'))):
            if bit == '1':
                u = self.ancestor[k][u]
        if u == v:
            return u
        for anc in reversed(self.ancestor):
            if anc[u] != anc[v]:
                u = anc[u]
                v = anc[v]
        return self.ancestor[0][u]



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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])


# 気合で木にする。（LCAを使いたいから。）
q = [1]
pseudo_parent = [0] * (N+1)
pseudo_parent[1] = 1
pseudo_adj = [[] for _ in range(N)] #This is 0-indexed.
while q:
    nq = []
    for v in q:
        for nv in inv_ABs[v]:
            if pseudo_parent[nv] == 0:
                pseudo_parent[nv] = v
                pseudo_adj[v-1].append(nv-1)
                pseudo_adj[nv-1].append(v-1)
                nq.append(nv)
    q = nq

lca = LCA(pseudo_adj)

odd_nodes = set((i for i, e in enumerate(iseven) if not e))
while odd_nodes:
    u = odd_nodes.pop()
    v = odd_nodes.pop()
    a = lca.lca(u-1, v-1) + 1
    while u != a:
        p = pseudo_parent[u]
        reverse_ABs[inv_ABs[u][p]] = (not reverse_ABs[inv_ABs[u][p]])
        u = p
    while v != a:
        p = pseudo_parent[v]
        reverse_ABs[inv_ABs[v][p]] = (not reverse_ABs[inv_ABs[v][p]])
        v = p    
    assert len(odd_nodes) % 2 == 0

for rflg, (A, B) in zip(reverse_ABs, ABs):
    if rflg:
        print(B, A)
    else:
        print(A, B)

Fixed submission:
# Euler Tourとimos法で殴る。
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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])


# Euler Tour
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])

# print(et)

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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

input = sys.stdin.buffer.readline

class LCA:
    "0-indexed"

    def __init__(self, adj):  
        N = len(adj) 
        parent = [-1] * N
        self.depth = [0] * N
        q = deque([0])
        while q:
            node = q.popleft()
            for next_node in adj[node]:
                if parent[node] != next_node:
                    parent[next_node] = node
                    q.append(next_node)
                    self.depth[next_node] = self.depth[node] + 1
                        
        self.ancestor = [parent] #self.ancestor[k][u]はuの2**k先の祖先。
        k = 1
        while (1 << k) < N:
            anc_k = [0] * N
            for u in range(N):
                if self.ancestor[-1][u] == -1:
                    anc_k[u] = -1
                else:
                    anc_k[u] = self.ancestor[-1][self.ancestor[-1][u]]
            self.ancestor.append(anc_k)
            k += 1

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        for k, bit in enumerate(reversed(format(self.depth[u]-self.depth[v], 'b'))):
            if bit == '1':
                u = self.ancestor[k][u]
        if u == v:
            return u
        for anc in reversed(self.ancestor):
            if anc[u] != anc[v]:
                u = anc[u]
                v = anc[v]
        return self.ancestor[0][u]



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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])

for A, B in ABs:
    if not iseven[A] and not iseven[B]:
        iseven[A] = True
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = (not reverse_ABs[inv_ABs[A][B]])


# 気合で木にする。（LCAを使いたいから。）
q = [1]
pseudo_parent = [0] * (N+1)
pseudo_parent[1] = 1
pseudo_adj = [[] for _ in range(N)] #This is 0-indexed.
while q:
    nq = []
    for v in q:
        for nv in inv_ABs[v]:
            if pseudo_parent[nv] == 0:
                pseudo_parent[nv] = v
                pseudo_adj[v-1].append(nv-1)
                pseudo_adj[nv-1].append(v-1)
                nq.append(nv)
    q = nq

lca = LCA(pseudo_adj)

odd_nodes = set((i for i, e in enumerate(iseven) if not e))
while odd_nodes:
    u = odd_nodes.pop()
    v = odd_nodes.pop()
    a = lca.lca(u-1, v-1) + 1
    while u != a:
        p = pseudo_parent[u]
        reverse_ABs[inv_ABs[u][p]] = (not reverse_ABs[inv_ABs[u][p]])
        u = p
    while v != a:
        p = pseudo_parent[v]
        reverse_ABs[inv_ABs[v][p]] = (not reverse_ABs[inv_ABs[v][p]])
        v = p    

for rflg, (A, B) in zip(reverse_ABs, ABs):
    if rflg:
        print(B, A)
    else:
        print(A, B)

Fixed submission:
# Euler Tourとimos法で殴る。
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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])


# Euler Tour
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])

# print(et)

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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

input = sys.stdin.buffer.readline

class LCA:
    "0-indexed"

    def __init__(self, adj):  
        N = len(adj) 
        parent = [-1] * N
        self.depth = [0] * N
        q = deque([0])
        while q:
            node = q.popleft()
            for next_node in adj[node]:
                if parent[node] != next_node:
                    parent[next_node] = node
                    q.append(next_node)
                    self.depth[next_node] = self.depth[node] + 1
                        
        self.ancestor = [parent] #self.ancestor[k][u]はuの2**k先の祖先。
        k = 1
        while (1 << k) < N:
            anc_k = [0] * N
            for u in range(N):
                if self.ancestor[-1][u] == -1:
                    anc_k[u] = -1
                else:
                    anc_k[u] = self.ancestor[-1][self.ancestor[-1][u]]
            self.ancestor.append(anc_k)
            k += 1

    def lca(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        for k, bit in enumerate(reversed(format(self.depth[u]-self.depth[v], 'b'))):
            if bit == '1':
                u = self.ancestor[k][u]
        if u == v:
            return u
        for anc in reversed(self.ancestor):
            if anc[u] != anc[v]:
                u = anc[u]
                v = anc[v]
        return self.ancestor[0][u]



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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])


# 気合で木にする。（LCAを使いたいから。）
q = [1]
pseudo_parent = [0] * (N+1)
pseudo_parent[1] = 1
pseudo_adj = [[] for _ in range(N)] #This is 0-indexed.
while q:
    nq = []
    for v in q:
        for nv in inv_ABs[v]:
            if pseudo_parent[nv] == 0:
                pseudo_parent[nv] = v
                pseudo_adj[v-1].append(nv-1)
                pseudo_adj[nv-1].append(v-1)
                nq.append(nv)
    q = nq

lca = LCA(pseudo_adj)

odd_nodes = set((i for i, e in enumerate(iseven) if not e))
while odd_nodes:
    u = odd_nodes.pop()
    v = odd_nodes.pop()
    a = lca.lca(u-1, v-1) + 1
    while u != a:
        p = pseudo_parent[u]
        reverse_ABs[inv_ABs[u][p]] = (not reverse_ABs[inv_ABs[u][p]])
        u = p
    while v != a:
        p = pseudo_parent[v]
        reverse_ABs[inv_ABs[v][p]] = (not reverse_ABs[inv_ABs[v][p]])
        v = p    

for rflg, (A, B) in zip(reverse_ABs, ABs):
    if rflg:
        print(B, A)
    else:
        print(A, B)

Fixed submission:
# Euler Tourとimos法で殴る。
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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])


# Euler Tour
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])

# print(et)

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)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline

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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])

odd_nodes = set((i for i, e in enumerate(iseven) if not e))


def bfs():
    global odd_nodes, reverse_ABs
    root = odd_nodes.pop()
    q = [root]
    parent = [0] * (N+1)
    parent[root] = root
    while q:
        nq = []
        for v in q:
            for nv in inv_ABs[v]:
                if parent[nv] == 0:
                    parent[nv] = v
                    nq.append(nv)
                if nv in odd_nodes: #reverse path between nv and root
                    v = nv
                    while parent[v] != v:
                        reverse_ABs[inv_ABs[parent[v]][v]] = (not reverse_ABs[inv_ABs[parent[v]][v]])
                        v = parent[v]
                    odd_nodes.remove(nv)
                    return
        q = nq


while odd_nodes:
    bfs()

for rflg, (A, B) in zip(reverse_ABs, ABs):
    if rflg:
        print(B, A)
    else:
        print(A, B)

Fixed submission:
# Euler Tourとimos法で殴る。
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]: # B -> A
        iseven[B] = True
        reverse_ABs[inv_ABs[A][B]] = True
    else:
        iseven[A] = (not iseven[A])


# Euler Tour
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])

# print(et)

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)