Problem p02976 (python)

Fixed submission:
#!/usr/bin/env python3
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')

#A
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

#B
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

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
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
    rank = defaultdict(lambda: inf)
    q = deque()
    q.append(0)
    rank[0] = 0
    while q:
        now = q.popleft()
        a = rank[now]
        for n in edg[now]:
            if rank[n] > a + 1:
                rank[n] = a + 1
                q.append(n)
    point = sorted(rank.items(),key = lambda x:x[1], reverse=True)
    for _,i in point:
        if ins[i] % 2:
            c = defaultdict(lambda: False)
            q = deque()
            q.append((i, [i]))
            c[i] = True
            while ins[i] % 2:
                now, route_ = q.popleft()
                for k in edg[now]:
                    if c[k] or rank[now] < rank[k]:
                        continue
                    c[k] = True
                    if ins[k] % 2:
                        route_.append(k)
                        for l in range(len(route_)-1):
                            a = route_[l]
                            b = route_[l + 1]
                            dag[(min(a, b), max(a, b))] ^= 1
                        ins[i] -= 1
                        ins[k] += 1
                        break
                    else:
                        q.append((k, route_ + [k]))
    for el1, el2 in dag.items():
        e1,e2 = el1
        if el2:
            print(e1 + 1, e2 + 1)
        else:
            print(e2 + 1, e1 + 1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
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: False)
            q = deque()
            q.append((i, [i]))
            c[i] = True
            while ins[i] % 2:
                now, route_ = q.popleft()
                for k in edg[now]:
                    if c[k]:
                        continue
                    c[k] = False
                    if ins[k] % 2:
                        route_.append(k)
                        for l in range(len(route_)-1):
                            a = route_[l]
                            b = route_[l + 1]
                            dag[(min(a, b), max(a, b))] ^= 1
                        ins[i] -= 1
                        ins[k] += 1
                        break
                    else:
                        q.append((k, now, route_ + [k]))
    for el1, el2 in dag.items():
        e1,e2 = el1
        if el2:
            print(e1 + 1, e2 + 1)
        else:
            print(e2 + 1, e1 + 1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    dag = defaultdict(list)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
        dag[a].append(b)
        ins[a] += 1
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i, -1 ,[i]))
            while ins[i] % 2:
                now, pre, route_ = q.popleft()
                for k in edg[now]:
                    if pre == k:
                        continue
                    if ins[k] % 2:
                        route_.append(k)
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if b in dag[a]:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] += 1
                        break
                    else:
                        q.append((k, now, route_+[k]))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    c[0] = 1
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[i]:
                    dag[now].append(i)
                    c[i] = 1
                    q.appendleft((i, now))
                    ins[now] += 1
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i, -1 ,[i]))
            while ins[i] % 2:
                now, pre, route_ = q.pop()
                for k in edg[now]:
                    if pre == k:
                        continue
                    route = route_[::1]
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if b in dag[a]:
                                dag[a].remove(b)
                                dag[b].append(a)
                            elif a in dag[b]:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] += 1
                        break
                    else:
                        q.append((k, now, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    c[0] = 1
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[i]:
                    dag[now].append(i)
                    c[i] = 1
                    q.appendleft((i, now))
                    ins[now] += 1
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i, -1 ,[i]))
            while ins[i] % 2:
                now, pre, route_ = q.popleft()
                for k in edg[now]:
                    if pre == k:
                        continue
                    route = route_[::1]
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if b in dag[a]:
                                dag[a].remove(b)
                                dag[b].append(a)
                            elif a in dag[b]:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] += 1
                        break
                    else:
                        q.append((k, now, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    c[0] = 1
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[i]:
                    dag[now].append(i)
                    c[i] = 1
                    q.appendleft((i, now))
                    ins[now] += 1
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i, -1 ,[i]))
            while ins[i] % 2:
                now, pre, route_ = q.popleft()
                for k in edg[now]:
                    if pre == k:
                        continue
                    route = route_[::1]
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if b in dag[a]:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] += 1
                        break
                    else:
                        q.append((k, now, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    c[0] = 1
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[i]:
                    dag[now].append(i)
                    c[i] = 1
                    q.append((i, now))
                    ins[now] += 1
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i, -1 ,[i]))
            while ins[i] % 2:
                now, pre, route_ = q.popleft()
                for k in edg[now]:
                    if pre == k:
                        continue
                    route = route_[::1]
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if b in dag[a]:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] += 1
                        break
                    else:
                        q.append((k, now, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    c[0] = 1
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[i]:
                    dag[now].append(i)
                    c[i] = 1
                    q.append((i, now))
                    ins[now] += 1
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i,[i]))
            while ins[i] % 2:
                now, route_ = q.popleft()
                for k in edg[now]:
                    route = route_[::1]
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if b in dag[a]:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] += 1
                        break
                    else:
                        q.append((k, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    c[0] = 1
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[i]:
                    dag[now].append(i)
                    c[i] = 1
                    q.append((i, now))
                    ins[now] += 1
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i,[i]))
            while ins[i] % 2:
                now, route_ = q.popleft()
                for k in edg[now]:
                    route = route_[::1]
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if b in dag[a]:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] -= 1
                        break
                    else:
                        q.append((k, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    c[0] = 1
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[i]:
                    dag[now].append(i)
                    c[i] = 1
                    q.append((i, now))
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i,[i]))
            while ins[i] % 2:
                now, route_ = q.popleft()
                for k in edg[now]:
                    route = route_[::1]
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if dag[a] in b:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] -= 1
                        break
                    else:
                        q.append((k, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    c[0] = 1
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[i]:
                    dag[now].append(i)
                    c[i] = 1
                    q.append((i, now))
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i,[i]))
            while ins[i] % 2:
                now, route = q.popleft()
                route = route[::1]
                for k in edg[now]:
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if dag[a] in b:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] -= 1
                        break
                    else:
                        q.append((k, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[(now, i)]:
                    c[(now, i)] = 1
                    dag[now].append(i)
                    q.append((i, now))
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i,[i]))
            while ins[i] % 2:
                now, route = q.popleft()
                route = route[::1]
                for k in edg[now]:
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if dag[a] in b:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] -= 1
                        break
                    else:
                        q.append((k, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[(now, i)]:
                    c[(now, i)] = 1
                    dag[now].append(i)
                    q.append((i, now))
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i,[i]))
            while ins[i] % 2:
                now, route = q.popleft()
                route = route[::1]
                for k in edg[now]:
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if dag[a] in b:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] -= 1
                    else:
                        q.append((k, route))
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
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')

#A
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

#B
def B():
    n, m = LI()
    if m % 2:
        print(-1)
        return
    edg = [[] for _ in range(n)]
    ins = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    dag = defaultdict(list)
    c = defaultdict(int)
    q = deque()
    for i in edg[0]:
        q.append((i, 0))
        dag[0].append(i)
        ins[0] += 1
    while q:
        now, per = q.pop()
        for i in edg[now]:
            if i != per:
                if not c[(now, i)]:
                    c[(now, i)] = 1
                    dag[now].append(i)
                    q.append((i, now))
    for i in range(n):
        if ins[i] % 2:
            q = deque()
            q.append((i,[i]))
            while ins[i] % 2:
                now, route = q.popleft()
                route = route[::1]
                for k in edg[now]:
                    route.append(k)
                    if ins[k] % 2:
                        for l in range(len(route)-1):
                            a = route[l]
                            b = route[l + 1]
                            if dag[a] in b:
                                dag[a].remove(b)
                                dag[b].append(a)
                            else:
                                dag[b].remove(a)
                                dag[a].append(b)
                        ins[i] -= 1
                        ins[k] -= 1
                    else:
                        q.append((k, route))
    print(dag)
    for e1,el2 in dag.items():
        for e2 in el2:
            print(e1+1,e2+1)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()