Problem: Eulerian Flight Tour

You have an airline route map of a certain region. All the airports in the region and all the non-stop routes between them are on the map. Here, a non-stop route is a flight route that provides non-stop flights in both ways.

Named after the great mathematician Leonhard Euler, an Eulerian tour is an itinerary visiting all the airports in the region taking a single flight of every non-stop route available in the region. To be precise, it is a list of airports, satisfying all of the following.

* The list begins and ends with the same airport.
* There are non-stop routes between pairs of airports adjacent in the list.
* All the airports in the region appear at least once in the list. Note that it is allowed to have some airports appearing multiple times.
* For all the airport pairs with non-stop routes in between, there should be one and only one adjacent appearance of two airports of the pair in the list in either order.



It may not always be possible to find an Eulerian tour only with the non-stop routes listed in the map. Adding more routes, however, may enable Eulerian tours. Your task is to find a set of additional routes that enables Eulerian tours.

Input

The input consists of a single test case.


$n$ $m$
$a_1$ $b_1$
...
$a_m$ $b_m$


$n$ ($3 \leq n \leq 100$) is the number of airports. The airports are numbered from 1 to $n$. $m$ ($0 \leq m \leq \frac{n(n-1)}{2}$) is the number of pairs of airports that have non-stop routes. Among the $m$ lines following it, integers $a_i$ and $b_i$ on the $i$-th line of them ($1 \leq i \leq m$) are airport numbers between which a non-stop route is operated. You can assume $1 \leq a_i < b_i \leq n$, and for any $i \ne j$, either $a_i \ne a_j$ or $b_i \ne b_j$ holds.

Output

Output a set of additional non-stop routes that enables Eulerian tours. If two or more different sets will do, any one of them is acceptable. The output should be in the following format.


$k$
$c_1$ $d_1$
...
$c_k$ $d_k$


$k$ is the number of non-stop routes to add, possibly zero. Each of the following $k$ lines should have a pair of integers, separated by a space. Integers $c_i$ and $d_i$ in the $i$-th line ($c_i < d_i$) are airport numbers specifying that a non-stop route is to be added between them. These pairs, ($c_i, d_i$) for $1 \leq i \leq k$, should be distinct and should not appear in the input.

If adding new non-stop routes can never enable Eulerian tours, output -1 in a line.

Sample Input 1


4 2
1 2
3 4


Sample Output 1


2
1 4
2 3


Sample Input 2


6 9
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6


Sample Output 2


-1


Sample Input 3


6 7
1 2
1 3
1 4
2 3
4 5
4 6
5 6


Sample Output 3


3
1 5
2 4
2 5


Sample Input 4


4 3
2 3
2 4
3 4


Sample Output 4


-1


Sample Input 5


5 5
1 3
1 4
2 4
2 5
3 5


Sample Output 5


0






Example

Input

4 2
1 2
3 4


Output

2
1 4
2 3

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 105

struct Edge{

	bool operator<(const struct Edge &arg) const{
		if(from != arg.from){

			return from < arg.from;
		}else{

			return to < arg.to;
		}
	}

	Edge(int arg_from,int arg_to){
		from = arg_from;
		to = arg_to;
	}
	int from,to;
};

int V,E;
int table[NUM]; //ノードから出ている辺の数
int boss[NUM],height[NUM],member_num[NUM];
int num_add[NUM];
int parent[NUM]; //偶奇の木における親
bool check[NUM][NUM],visited[NUM],is_GU[NUM];
vector<int> MEMBER[NUM];
vector<Edge> neg_G[NUM],ans;

//自分のボスのindexを取得しつつ、経路圧縮を行う関数
int get_boss(int id){
	if(boss[id] == id)return id; //自分が代表なら、自分の値を返す
	else{
		return boss[id] = get_boss(boss[id]); //代表でないなら、自分が所属する組織の代表を返しつつ、経路圧縮
	}
}

int is_same(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	//既に同じグループなら何もしない
	if(boss_x == boss_y)return;

	//高さが高い方に吸収する
	if(height[x] > height[y]){

		member_num[boss_x] += member_num[boss_y];
		boss[boss_y] = boss_x;

	}else if(height[x] < height[y]){

		member_num[boss_y] += member_num[boss_x];
		boss[boss_x] = boss_y;

	}else{ //height[x] == height[y]

		member_num[boss_x] += member_num[boss_y];
		boss[boss_y] = boss_x;
		height[x]++;
	}
}

void dfs(int node_id,int pre_node){

	for(int next = 0; next < V; next++){

		if(visited[next] == true || check[node_id][next] == true)continue;

		visited[next] = true;

		dfs(next,node_id);
	}

	if(!is_GU[node_id]){ //ここで、グループ間をまたぐ辺を張り得る
		if(pre_node != -1){
			ans.push_back(Edge(min(node_id,pre_node),max(node_id,pre_node)));

			unite(node_id,pre_node); //★注意★

			is_GU[node_id] = true;
			is_GU[pre_node] = 1-is_GU[pre_node];

			check[node_id][pre_node] = true;
			check[pre_node][node_id] = true;

			table[node_id]++;
			table[pre_node]++;
		}
	}
}

void outPut(){

	sort(ans.begin(),ans.end());

	printf("%lld\n",ans.size());

	for(int i = 0; i < ans.size(); i++){

		printf("%d %d\n",ans[i].from+1,ans[i].to+1);
	}
}

int main(){


	scanf("%d %d",&V,&E);

	for(int i = 0; i < V; i++){

		table[i] = 0;
	}

	for(int from = 0; from < V; from++){
		for(int to = 0; to < V; to++){

			check[from][to] = (from==to); //from-toに辺があるか
		}
	}

	for(int i = 0; i < V; i++){

		boss[i] = i;
		height[i] = i;
		member_num[i] = 1;
	}

	int from,to;

	for(int loop = 0; loop < E; loop++){

		scanf("%d %d",&from,&to);

		from--;
		to--;

		table[from]++;
		table[to]++;

		check[from][to] = true;
		check[to][from] = true;

		unite(from,to);
	}



	for(int i = 0; i < V; i++){

		is_GU[i] = (table[i]%2 == 0); //次数が偶数かどうか
		visited[i] = false;
	}

	vector<int> ROOT;

	//補グラフを作る
	for(int i = 0; i < V; i++){
		if(visited[i])continue;

		visited[i] = true;
		ROOT.push_back(i);
		dfs(i,-1);
	}



	for(int i = 0; i < ROOT.size(); i++){

		if(!is_GU[ROOT[i]]){

			printf("-1\n");
			return 0;
		}
	}

	//グループ数を数える
	vector<int> BOSS;

	for(int i = 0; i < V; i++){
		if(i == get_boss(i)){
			BOSS.push_back(i);
		}
	}

	for(int i = 0; i < V; i++){

		MEMBER[get_boss(i)].push_back(i); //メンバーを取得
	}

	if(BOSS.size() == 1){

		outPut();

	}else if(BOSS.size() == 2){ //コーナーケースあり

		if(member_num[BOSS[0]] > member_num[BOSS[1]])swap(BOSS[0],BOSS[1]);
		for(int i = 0; i < V; i++)MEMBER[i].clear();

		for(int i = 0; i < V; i++){

			MEMBER[get_boss(i)].push_back(i); //メンバーを取得
		}

		//2つのグループのサイズがいずれも2以上か
		vector<int> P;

		P.push_back(member_num[BOSS[0]]);
		P.push_back(member_num[BOSS[1]]);

		if(P[0] >= 2){

			//グループ同士を結んで連結にする
			ans.push_back(Edge(min(MEMBER[BOSS[0]][0],MEMBER[BOSS[1]][0]),max(MEMBER[BOSS[0]][0],MEMBER[BOSS[1]][0])));
			ans.push_back(Edge(min(MEMBER[BOSS[0]][0],MEMBER[BOSS[1]][1]),max(MEMBER[BOSS[0]][0],MEMBER[BOSS[1]][1])));

			ans.push_back(Edge(min(MEMBER[BOSS[0]][1],MEMBER[BOSS[1]][0]),max(MEMBER[BOSS[0]][1],MEMBER[BOSS[1]][0])));
			ans.push_back(Edge(min(MEMBER[BOSS[0]][1],MEMBER[BOSS[1]][1]),max(MEMBER[BOSS[0]][1],MEMBER[BOSS[1]][1])));
			outPut();

		}else{


			if(P[0] == 1 && P[1]%2 == 1){ //コーナーケース

				if(E+ans.size() == (member_num[BOSS[1]])*(member_num[BOSS[1]]-1)/2){ //完全グラフ+孤立点なら不可
					printf("-1\n");

				}else{

					vector<int> D;
					//次数がノード数-1でない、偶数頂点をピックアップ
					for(int i = 0; i < MEMBER[BOSS[1]].size(); i++){
						if(table[MEMBER[BOSS[1]][i]] < MEMBER[BOSS[1]].size()-1){
							D.push_back(MEMBER[BOSS[1]][i]);
						}
					}

					for(int i = 0; i < V; i++){

						visited[i] = false;
					}

					//とりあえず直線を作る
					queue<int> Q;

					int start = D[0],end = D[1];
					visited[start] = true;

					Q.push(start);

					while(!Q.empty()){

						end = Q.front();

						for(int next = 0; next < D.size(); next++){
							if(visited[D[next]] == true || check[Q.front()][D[next]] == true)continue;

							visited[D[next]] = true;
							ans.push_back(Edge(min(Q.front(),D[next]),max(Q.front(),D[next])));
							check[Q.front()][D[next]] = true;
							check[D[next]][Q.front()] = true;
							Q.push(D[next]);
							break;
						}

						Q.pop();
					}

					//孤立点からstart-endを結んで輪にする
					ans.push_back(Edge(min(BOSS[0],start),max(BOSS[0],start)));
					ans.push_back(Edge(min(BOSS[0],end),max(BOSS[0],end)));

					outPut();
				}

			}else{ //1+偶数

				//すべての頂点に辺を張る
				for(int i = 0; i < MEMBER[BOSS[1]].size(); i++){

					ans.push_back(Edge(min(BOSS[0],MEMBER[BOSS[1]][i]),max(BOSS[0],MEMBER[BOSS[1]][i])));
				}

				//偶数の方を、完全グラフにする(★次数を奇数にするため→孤立点との辺で偶数になる★)
				for(int i = 0; i < MEMBER[BOSS[1]].size(); i++){
					from = MEMBER[BOSS[1]][i];
					for(int k = i+1; k < MEMBER[BOSS[1]].size(); k++){
						to = MEMBER[BOSS[1]][k];

						if(check[from][to])continue;

						check[from][to] = true;
						check[to][from] = true;

						ans.push_back(Edge(min(from,to),max(from,to)));
					}
				}

				outPut();
			}
		}

	}else{

		//ボス同士を結んで連結にする
		for(int i = 0; i < BOSS.size(); i++){

			ans.push_back(Edge(min(BOSS[i],BOSS[(i+1)%BOSS.size()]),max(BOSS[i],BOSS[(i+1)%BOSS.size()])));
		}

		outPut();
	}

	return 0;
}