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>

using namespace std;

using vec = vector<int>;
using mat = vector<vec>;
using Pi = pair<int, int>;

struct UnionFind {
  vec data;
  UnionFind(int n):data(n, -1){}
  int find(int x) {
    return data[x] < 0 ? x : data[x] = find(data[x]);
  }
  int size(int x) {
    return -data[find(x)];
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  mat G(n, vec(n, 0));
  UnionFind uf(n);
  vec deg(n);
  for(int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    G[a][b] = G[b][a] = 1;
    uf.unite(a, b);
    deg[a]++;
    deg[b]++;
  }

  auto isEuler = [&](vec V) {
    for(int v : V) if(deg[v]&1) return false;
    return true;
  };

  {
    vec V(n);
    iota(V.begin(), V.end(), 0);
    if(uf.size(0) == n && isEuler(V)) {
      cout << 0 << endl;
      return 0;
    }
  }

  vector<Pi> ans;

  if(n&1) {
    for(int i = 0; i < n; ++i) {
      for(int j = i+1; j < n; ++j) {
	if(!G[i][j]) {
	  G[i][j] = G[j][i] = 1;
	  ans.emplace_back(i, j);
	}
      }
    }
    cout << ans.size() << endl;
    for(Pi p : ans) cout << p.first+1 << " " << p.second+1 << endl;
    return 0;
  }

  vector<vec> eulers;
  vector<vec> not_eulers;
  for(int i = 0; i < n; ++i) {
    if(uf.find(i) != i) continue;
    vec V;
    for(int j = 0; j < n; ++j) if(uf.find(j) == i) V.push_back(j);
    if(isEuler(V)) eulers.push_back(V);
    else not_eulers.push_back(V);
  }

  if(!not_eulers.empty()) {
    vector<vec> odd;
    for(vec& V : not_eulers) {
      odd.push_back({});
      for(int v : V) {
	if(deg[v]&1) odd.back().push_back(v);
      }
    }
    if(!eulers.empty()) {
      vec& EV = eulers[0];
      int u = EV[0];
      for(int i = 0; i < (int)not_eulers.size(); ++i) {
	vec& V = not_eulers[i];
	for(int o : odd[i]) {
	  G[u][o] = G[o][u] = 1;
	  ans.push_back(minmax(u, o));
	}
	EV.insert(EV.end(), V.begin(), V.end());
      }
    } else if(not_eulers.size() == 1) {
      vec& V = not_eulers[0];
      UnionFind uf2(n);
      for(int u : V) {
	for(int v : V) {
	  if(u == v) continue;
	  if(!G[u][v]) uf2.unite(u, v);
	}
      }

      mat H(n, vec(n, 0));
      vec vis(n, 0);
      function<bool(int, int)> dfs = [&](int u, int v) {
	vis[u] = 1;
	if(u == v) return true;
	for(int i = 0; i < n; ++i) {
	  if(u == i) continue;
	  if(!vis[i] && !G[u][i]) {
	    H[u][i] = 1-H[u][i];
	    H[i][u] = 1-H[i][u];
	    if(dfs(i, v)) return true;
	    H[u][i] = 1-H[u][i];
	    H[i][u] = 1-H[i][u];
	  }
	}
	return false;
      };

      vec used(n, 0);
      for(int u : odd[0]) {
	if(used[u]) continue;
	for(int v : odd[0]) {
	  if(u == v || used[v]) continue;
	  if(uf2.same(u, v)) {
	    fill(vis.begin(), vis.end(), 0);
	    if(dfs(u, v)) {
	      used[u] = used[v] = 1;
	      break;
	    }
	  }
	}
      }
      for(int v : odd[0]) {
	if(!used[v]) {
	  cout << -1 << endl;
	  return 0;
	}
      }

      for(int i = 0; i < n; ++i) {
	for(int j = i+1; j < n; ++j) {
	  if(H[i][j]) {
	    G[i][j] = G[j][i] = 1;
	    ans.emplace_back(i, j);
	  }
	}
      }
      eulers.push_back(V);
    } else {
      int idx = 0;
      for(int i = 1; i < (int)not_eulers.size(); ++i) {
	if(odd[i].size() < odd[idx].size()) idx = i;
      }
      vec V, U;
      for(int i = 0; i < (int)not_eulers.size(); ++i) {
	if(i == idx) continue;
	for(int v : odd[i]) {
	  if(V.size() < odd[idx].size()) V.push_back(v);
	  else U.push_back(v);
	}
      }
      for(int i = 0; i < (int)V.size(); ++i) {
	G[odd[idx][i]][V[i]] = G[V[i]][odd[idx][i]] = 1;
	ans.push_back(minmax(odd[idx][i], V[i]));
      }
      for(int v : U) {
	G[odd[idx][0]][v] = G[v][odd[idx][0]] = 1;
	ans.push_back(minmax(odd[idx][0], v));
      }
      eulers.push_back(vec(n));
      iota(eulers.back().begin(), eulers.back().end(), 0);
    }
  }

  auto isPerfect = [&](vec V) {
    for(int u : V) {
      int cnt = 0;
      for(int v : V) cnt += G[u][v];
      if(cnt+1 != (int)V.size()) return false;
    }
    return true;
  };

  if(eulers.size() == 2) {
    if((eulers[0].size() == 1 && isPerfect(eulers[1])) ||
       (eulers[1].size() == 1 && isPerfect(eulers[0]))) {
      cout << -1 << endl;
      return 0;
    } else if(eulers[0].size() == 1 || eulers[1].size() == 1) {
      int u = eulers[eulers[1].size() == 1][0];
      bool flag = true;
      for(int i = 0; i < n; ++i) {
	if(i == u) continue;
	for(int j = i+1; j < n; ++j) {
	  if(j == u) continue;
	  if(!G[i][j]) {
	    //if(flag) {
	    if(u==-1){
	      G[i][j] = G[j][i] = 1;
	      ans.emplace_back(i, j);
	    } else {
	      G[i][u] = G[u][i] = G[u][j] = G[j][u] = 1;
	      ans.push_back(minmax(i, u));
	      ans.push_back(minmax(u, j));
	      //flag = false;
	      u = -1;
	    }
	  }
	}
      }

      for(int i = 0; i < n; ++i) {
	int cnt = 0;
	for(int j = 0; j < n; ++j) cnt += G[i][j];
	if(cnt&1) flag=false;//assert(false);
      }
      if(!flag) {
	cout<<-1<<endl;
	return 0;
      }

    } else {
      for(int i = 0; i < 2; ++i) {
	for(int j = 0; j < 2; ++j) {
	  G[eulers[0][i]][eulers[1][j]] = G[eulers[1][j]][eulers[0][i]] = 1;
	  ans.push_back(minmax(eulers[0][i], eulers[1][j]));
	}
      }
    }
  } else if(eulers.size() > 2) {
    int sz = eulers.size();
    for(int i = 0; i < sz; ++i) {
      G[eulers[i][0]][eulers[(i+1)%sz][0]] = G[eulers[(i+1)%sz][0]][eulers[i][0]] = 1;
      ans.push_back(minmax(eulers[i][0], eulers[(i+1)%sz][0]));
    }
  }

  for(int i = 0; i < n; ++i) {
    int cnt = 0;
    for(int j = 0; j < n; ++j) cnt += G[i][j];
    if(cnt&1) assert(false);
  }

  cout << ans.size() << endl;
  for(Pi p : ans) cout << p.first+1 << " " << p.second+1 << endl;

  return 0;
}