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

Solution:
// Do you knOW what it feels like?

		// To be TorTured by your own MinD?
	
	// I don't wanna feel the PAIN.

// I BeG you KILLING me, pleASE...

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())

typedef long long ll;
typedef pair<ll,ll> pll;

const ll maxn=1e5+10, mod=1e9+7, inf=1e18;

vector<ll> g[maxn];

set<pll> all;
ll out[maxn];
bool mk[maxn];

void pfs(ll v=1){
	mk[v]=1;
	for(auto u:g[v])if(!mk[u]){
		out[min(v,u)]--;
		all.erase({min(v,u),max(v,u)});
		pfs(u);
		if(out[u]%2){
			out[u]++;
			all.insert({u,v});
		}
		else{
			out[v]++;
			all.insert({v,u});
		}
	}
}

int main(){
	
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	ll n,m; cin>>n>>m;

	ll v,u;
	for(int i=0;i<m;i++){
		cin>>v>>u;

		if(v>u) swap(v,u);
		g[v].pb(u), g[u].pb(v);

		all.insert({v,u});
		out[v]++;
	}

	if(m%2) return cout<<-1, 0;

	pfs();

	for(auto x:all) cout<<x.F<<' '<<x.S<<endl;

	return 0;
}