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.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] A = new int[M];
		int[] B = new int[M];
		Vertice[] vs = new Vertice[N];
		for (int i = 0; i < N; ++i) {
			vs[i] = new Vertice(i);
		}
		for (int i = 0; i < M; ++i) {
			A[i] = sc.nextInt();
			B[i] = sc.nextInt();
			--A[i];
			--B[i];
			addEdge(vs[A[i]], vs[B[i]]);
		}
		vs[0].dfs(null);
		if (vs[0].deg == 1) {
			System.out.println(-1);
		} else {
			for (int i = 0; i < N; ++i) {
				for (Edge e : vs[i].outgo) {
					if (e.direction == 1) {
						System.out.println((i + 1) + " " + (e.dst.id + 1));
					}
				}
			}
		}
	}

	void addEdge(Vertice a, Vertice b) {
		Edge ab = new Edge();
		Edge ba = new Edge();
		ab.dst = b;
		ba.dst = a;
		ab.rev = ba;
		ba.rev = ab;
		a.outgo.add(ab);
		b.outgo.add(ba);
	}

	class Vertice {
		int id;
		int deg = 0;
		ArrayList<Edge> outgo = new ArrayList<>();
		boolean visited = false;

		public Vertice(int id_) {
			id = id_;
		}

		void dfs(Edge toParent) {
			visited = true;
			for (Edge e : outgo) {
				if (e == toParent) {
					continue;
				}
				if (!e.dst.visited) {
					e.dst.dfs(e.rev);
				} else if (e.direction < 0) {
					e.direction = 1;
					e.rev.direction = 0;
				}
				deg ^= e.direction;
			}
			if (toParent == null)
				return;
			toParent.direction = deg;
			toParent.rev.direction = 1 ^ deg;
			deg = 0;
		}
	}

	class Edge {
		Vertice dst;
		Edge rev;
		int direction = -1;
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}