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.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static class Edge {
        int a;
        int b;

        public Edge(int a, int b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge edge = (Edge) o;
            return a == edge.a &&
                    b == edge.b;
        }

        @Override
        public int hashCode() {
            return Objects.hash(a, b);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (int i = 0; i < m; ++i) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            Set<Integer> nextA = graph.getOrDefault(a, new HashSet<>());
            nextA.add(b);
            Set<Integer> nextB = graph.getOrDefault(b, new HashSet<>());
            nextB.add(a);
            graph.put(a, nextA);
            graph.put(b, nextB);
        }
        if (m % 2 == 1) {
            System.out.println(-1);
            return;
        }
        Set<Edge> edges = new HashSet<>();

        bfs(n, graph, edges);
        edges.forEach(
                edge -> System.out.println(edge.a + " " + edge.b)
        );

    }

    public static void bfs(int n, Map<Integer, Set<Integer>> graph, Set<Edge> edges) {
        Queue<Integer> nodes = new LinkedList<>();
        int[] order = new int[n + 1];
        nodes.add(1);
        int [] visited = new int[n + 1];
        int [] outDegrees = new int[n + 1];
        int [] father = new int[n + 1];
        visited[1] = 1;
        int i = 0;
        order[i++] = 1;
        while (!nodes.isEmpty()) {
            int current = nodes.poll();
          //  System.out.println("current: " + current);
            for (int son : graph.get(current)) {
              //  System.out.println("son: " + son);
                if (visited[son] == 0) {
                    order[i++] = son;
                    father[son] = current;
                    visited[son] = 1;
                    nodes.add(son);
               //     System.out.println("span: " + current + " -> " + son);
                } else {
                    if (son != father[current] &&
                            !edges.contains(new Edge(current, son)) &&
                        !edges.contains(new Edge(son, current))
                    ) {
                        edges.add(new Edge(current, son));
                   //     System.out.println("edge: " + current + "-> " + son);
                        outDegrees[current]++;
                    }
                }
            }
        }

        for (i = n - 1; i >= 1; --i) {
            int current = order[i];
            int currentFather = father[current];
        //    System.out.println("current: " + current + " father: " + currentFather);
            if (outDegrees[current] % 2 == 0) {
                edges.add(new Edge(currentFather, current));
                outDegrees[currentFather]++;
           //     System.out.println("edge: " + currentFather + "-> " + current);
            } else {
                edges.add(new Edge(current, currentFather));
                outDegrees[current]++;
          //      System.out.println("edge: " + current + "-> " + currentFather);
            }
        }
    }

}