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

Solution:
import java.awt.Point;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    static PrintWriter out = new PrintWriter(System.out, false);

    static Set<Point> set = new HashSet<>();
    static List<List<Integer>> edge = new ArrayList<>();
    static boolean[] visited;
    public static void main(String[]$) {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            edge.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt() - 1;
            int b = scanner.nextInt() - 1;
            edge.get(a).add(b);
            edge.get(b).add(a);
        }
        if (m % 2 == 1) {
            System.out.println(-1);
        } else {
            dfs(-1, 0);
        }
        out.flush();
    }

    static boolean dfs(int parent, int node) {
        visited[node] = true;
        int use = 0;
        for (int i : edge.get(node)) {
            if (i != parent && !set.contains(new Point(node, i)) && (visited[i] || dfs(node, i))) {
                set.add(new Point(i, node));
                out.println((node + 1) + " " + (i + 1));
                use++;
            }
        }
        if (use % 2 == 1 && parent != -1) {
            out.println((node + 1) + " " + (parent + 1));
        }
        return use % 2 == 0;
    }
}