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

    すべての辺はどこかの頂点から出なければならないので、辺の数が奇数だと作れない。
    偶数の場合は必ず構成できる。
    ・適当な根付き全域木を取り、残りの辺を適当に向き付ける
    ・木の頂点vとその親を結ぶ辺の向きを決めるときは、vの出次数が偶数になるようにする
    これで、根以外の出次数は偶数になっており、根の出次数は、全体の出次数の
    和が偶数であることから偶数である。
    """
    # 参考: https://atcoder.jp/contests/agc035/submissions/6392673
    if M % 2 == 1:
        return -1

    import sys
    sys.setrecursionlimit(10**6)

    # 以下、1-basedとする
    graph = [[] for _ in range(N + 1)]
    for a, b in Edges:
        graph[a].append(b)
        graph[b].append(a)

    def make_spanning_tree(current, ret=None, is_visit=None):
        if ret is None:
            ret = [set() for _ in range(N + 1)]  # ret[v]: 頂点vの子の集合
        if is_visit is None:
            is_visit = [False] * (N + 1)
            is_visit[current] = True

        for next_vertex in graph[current]:
            if is_visit[next_vertex]:
                continue
            ret[current].add(next_vertex)
            is_visit[next_vertex] = True
            ret = make_spanning_tree(next_vertex, ret, is_visit)
        return ret

    # 全域木の構成
    root_vertex = 1
    spanning_tree = make_spanning_tree(root_vertex)

    # 出次数の計算
    outdegree = [0] * (N + 1)
    ans = []
    # 全域木に使わなかった辺は a -> b となるように向きをつける
    for a, b in Edges:
        if a not in spanning_tree[b] and b not in spanning_tree[a]:
            ans.append((a, b))
            outdegree[a] += 1

    def dfs(current):
        # 全域木の current - child を結ぶ辺に向きをつける
        # 葉から考えれば、出次数の帳尻を合わせるように辺の向きを決めればよくなる
        for child in spanning_tree[current]:
            if spanning_tree[child]:
                dfs(child)  # currentが葉でない場合
            if outdegree[child] % 2 == 0:
                ans.append((current, child))
                outdegree[current] += 1
            else:
                ans.append((child, current))
                outdegree[child] += 1

    dfs(root_vertex)
    ans.sort()  # 本質的にはいらない
    return '\n'.join(' '.join(map(str, row)) for row in ans)

N, M = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(M)]
print(b_even_degrees(N, M, Edges))