Problem: 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.

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.

Examples

Input

4 4
1 2
2 3
3 4
4 1


Output

1 2
1 4
3 2
3 4


Input

5 5
1 2
2 3
3 4
2 5
4 5


Output

-1

Solution (in PYTHON3):

Solution:
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]


N, M = map(int, input().split())
if M%2==1:
    print(-1)
    exit()
E = [set() for _ in range(N+1)]
E_mst = [set() for _ in range(N+1)]
#Closed = [False] * (N+1)
uf = Uf(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    E[a].add(b)
    E[b].add(a)
    if not uf.same(a, b):
        E_mst[a].add(b)
        E_mst[b].add(a)
        uf.unite(a, b)

Cnt = [len(e) for e in E_mst]
q = {i for i, c in enumerate(Cnt) if c==1}
Used = set()
Ans = []
while q:

    v = q.pop()

    #print(E_mst, v)
    # vp = None#E_mst[v][0]
    # for vp_ in E_mst[v]:
    #     if not ((v,vp_) if v<vp_ else (vp_,v)) in Used:
    #         vp = vp_
    #         break
    # else:
    #     break

    if len(E_mst[v])==1:
        vp = E_mst[v].pop()
    else:
        vp = -1

    l = len(E[v])
    #print(v, l)
    for u in E[v].copy():
        if u!=vp:
            v_, u_ = (v,u) if v<u else (u,v)
            if (v_, u_) not in Used:
                Ans.append((v, u))
                E[u].remove(v)
                E[v].remove(u)
                Used.add((v_, u_))
    if l%2==0:
        try:
            E[vp].remove(v)
            E[v].remove(vp)
        except:
            break
        Ans.append((v, vp))
        Used.add((v,vp) if v<vp else (vp,v))
    # Cnt[vp] -= 1
    # if Cnt[vp]==1:
    #     q.add(vp)
    #print(Cnt)

    E_mst[vp].remove(v)
    if len(E_mst[vp])==1:
        q.add(vp)


#print(E_mst)
if len(Ans)!=M:
    print(Ans)
    print(-1)
    assert False
    exit()
for a in Ans:
    print(" ".join(map(str, a)))