Problem: I have an undirected graph consisting of n nodes, numbered 1 through n. Each node has at most two incident edges. For each pair of nodes, there is at most an edge connecting them. No edge connects a node to itself.

I would like to create a new graph in such a way that: 

  * The new graph consists of the same number of nodes and edges as the old graph. 
  * The properties in the first paragraph still hold. 
  * For each two nodes u and v, if there is an edge connecting them in the old graph, there is no edge connecting them in the new graph. 



Help me construct the new graph, or tell me if it is impossible.

Input

The first line consists of two space-separated integers: n and m (1 ≤ m ≤ n ≤ 105), denoting the number of nodes and edges, respectively. Then m lines follow. Each of the m lines consists of two space-separated integers u and v (1 ≤ u, v ≤ n; u ≠ v), denoting an edge between nodes u and v.

Output

If it is not possible to construct a new graph with the mentioned properties, output a single line consisting of -1. Otherwise, output exactly m lines. Each line should contain a description of edge in the same way as used in the input format.

Examples

Input

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


Output

1 4
4 6
1 6
2 7
7 5
8 5
2 8


Input

3 2
1 2
2 3


Output

-1


Input

5 4
1 2
2 3
3 4
4 1


Output

1 3
3 5
5 2
2 4

Note

The old graph of the first example:

<image>

A possible new graph for the first example:

<image>

In the second example, we cannot create any new graph.

The old graph of the third example:

<image>

A possible new graph for the third example:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int M = 100000 + 5;
vector<int> link2;
vector<int> link3;
vector<int> ring3;
vector<int> ring4;
vector<int> free2;
vector<int> linkans[M];
vector<int> ringans[M];
int linkcnt = 0;
int ringcnt = 0;
vector<int> adj[M];
int vis[M];
vector<int> component;
void dfs(int cur, int par) {
  component.push_back(cur);
  vis[cur] = 1;
  for (int i = 0; i < adj[cur].size(); i++) {
    int nxt = adj[cur][i];
    if (!vis[nxt] && nxt != par) {
      dfs(nxt, cur);
    }
  }
  return;
}
int main() {
  time_t t_start, t_end;
  t_start = clock();
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      if (adj[i].empty()) {
        vis[i] = 1;
        free2.push_back(i);
      } else {
        component.clear();
        dfs(i, 0);
        bool islink = false;
        int deg1 = -1;
        for (int j = 0; j < component.size(); j++) {
          int u = component[j];
          if (adj[u].size() == 1) {
            islink = true;
            deg1 = u;
            break;
          }
        }
        int sz = component.size();
        if (islink) {
          component.clear();
          for (int j = 0; j < sz; j++) {
            vis[component[j]] = 0;
          }
          dfs(deg1, 0);
          if (sz >= 4) {
            if (sz & 1) {
              for (int j = sz - 1; j >= 0; j = j - 2) {
                linkans[linkcnt].push_back(component[j]);
              }
              for (int j = sz - 2; j >= 0; j = j - 2) {
                linkans[linkcnt].push_back(component[j]);
              }
              linkcnt++;
            } else {
              for (int j = sz - 2; j >= 0; j = j - 2) {
                linkans[linkcnt].push_back(component[j]);
              }
              for (int j = sz - 1; j >= 0; j = j - 2) {
                linkans[linkcnt].push_back(component[j]);
              }
              linkcnt++;
            }
          } else {
            if (sz == 2) {
              for (int j = 0; j < sz; j++) {
                link2.push_back(component[j]);
              }
            } else {
              for (int j = 0; j < sz; j++) {
                link3.push_back(component[j]);
              }
            }
          }
        } else {
          if (sz >= 5) {
            if (sz & 1) {
              for (int j = sz - 2; j >= 0; j = j - 2) {
                ringans[ringcnt].push_back(component[j]);
              }
              for (int j = sz - 1; j >= 0; j = j - 2) {
                ringans[ringcnt].push_back(component[j]);
              }
              ringcnt++;
            } else {
              for (int j = sz - 2; j >= 4; j = j - 2) {
                ringans[ringcnt].push_back(component[j]);
              }
              ringans[ringcnt].push_back(component[0]);
              ringans[ringcnt].push_back(component[2]);
              for (int j = sz - 1; j >= 0; j = j - 2) {
                ringans[ringcnt].push_back(component[j]);
              }
              ringcnt++;
            }
          } else {
            if (sz == 4) {
              for (int j = 0; j < sz; j++) {
                ring4.push_back(component[j]);
              }
            } else {
              if (sz == 3) {
                for (int j = 0; j < sz; j++) {
                  ring3.push_back(component[j]);
                }
              }
            }
          }
        }
      }
    }
  }
  int sz = link2.size();
  if (sz >= 4) {
    for (int i = sz - 1; i >= 0 && sz >= 4; i = i - 4) {
      int u1 = link2[i];
      int v1 = link2[i - 1];
      int u2 = link2[i - 2];
      int v2 = link2[i - 3];
      linkans[linkcnt].push_back(u1);
      linkans[linkcnt].push_back(u2);
      linkcnt++;
      linkans[linkcnt].push_back(v1);
      linkans[linkcnt].push_back(v2);
      linkcnt++;
      for (int j = 0; j < 4; j++) {
        link2.pop_back();
      }
      sz -= 4;
    }
  }
  int link2sz = link2.size();
  sz = link3.size();
  if (sz >= 6) {
    for (int i = sz - 1; i >= 0 && sz >= 6; i = i - 6) {
      int u1 = link3[i];
      int v1 = link3[i - 1];
      int w1 = link3[i - 2];
      int u2 = link3[i - 3];
      int v2 = link3[i - 4];
      int w2 = link3[i - 5];
      linkans[linkcnt].push_back(u1);
      linkans[linkcnt].push_back(u2);
      linkans[linkcnt].push_back(v1);
      linkans[linkcnt].push_back(v2);
      linkcnt++;
      linkans[linkcnt].push_back(w1);
      linkans[linkcnt].push_back(w2);
      linkcnt++;
      for (int j = 0; j < 6; j++) {
        link3.pop_back();
      }
      sz -= 6;
    }
  }
  int link3sz = link3.size();
  sz = ring3.size();
  if (sz >= 6) {
    for (int i = sz - 1; i >= 0 && sz >= 6; i = i - 6) {
      int u1 = ring3[i];
      int v1 = ring3[i - 1];
      int w1 = ring3[i - 2];
      int u2 = ring3[i - 3];
      int v2 = ring3[i - 4];
      int w2 = ring3[i - 5];
      ringans[ringcnt].push_back(u1);
      ringans[ringcnt].push_back(v2);
      ringans[ringcnt].push_back(v1);
      ringans[ringcnt].push_back(w2);
      ringans[ringcnt].push_back(w1);
      ringans[ringcnt].push_back(u2);
      ringcnt++;
      for (int j = 0; j < 6; j++) {
        ring3.pop_back();
      }
      sz -= 6;
    }
  }
  int ring3sz = ring3.size();
  sz = ring4.size();
  if (sz >= 8) {
    for (int i = sz - 1; i >= 0 && sz >= 8; i = i - 8) {
      int u1 = ring4[i];
      int v1 = ring4[i - 1];
      int w1 = ring4[i - 2];
      int x1 = ring4[i - 3];
      int u2 = ring4[i - 4];
      int v2 = ring4[i - 5];
      int w2 = ring4[i - 6];
      int x2 = ring4[i - 7];
      ringans[ringcnt].push_back(u1);
      ringans[ringcnt].push_back(v2);
      ringans[ringcnt].push_back(v1);
      ringans[ringcnt].push_back(w2);
      ringans[ringcnt].push_back(w1);
      ringans[ringcnt].push_back(x2);
      ringans[ringcnt].push_back(x1);
      ringans[ringcnt].push_back(u2);
      ringcnt++;
      for (int j = 0; j < 8; j++) {
        ring4.pop_back();
      }
      sz -= 8;
    }
  }
  int ring4sz = ring4.size();
  bool ok = false;
  if (link2sz == 0 && link3sz == 0 && ring3sz == 0 && ring4sz == 0) {
    ok = true;
  }
  if (link2sz != 0 && link3sz == 0 && ring3sz == 0 && ring4sz == 0) {
    if (free2.size() > 0) {
      int x = free2[0];
      linkans[linkcnt].push_back(link2[0]);
      linkans[linkcnt].push_back(free2[0]);
      linkcnt++;
      ok = true;
    } else {
      if (linkcnt > 0) {
        linkans[0].push_back(link2[0]);
        ok = true;
      } else {
        if (ringcnt > 0) {
          ringans[0].push_back(link2[0]);
          ok = true;
        }
      }
    }
  }
  if (link2sz == 0 && link3sz != 0 && ring3sz == 0 && ring4sz == 0) {
    if (free2.size() > 0) {
      int x = free2[0];
      linkans[linkcnt].push_back(x);
      linkans[linkcnt].push_back(link3[1]);
      linkcnt++;
      ok = true;
    } else {
      if (ringcnt > 0) {
        ringans[0].push_back(link3[1]);
        ok = true;
      } else {
        if (linkcnt > 0) {
          linkans[0].push_back(link3[1]);
          ok = true;
        }
      }
    }
    linkans[linkcnt].push_back(link3[0]);
    linkans[linkcnt].push_back(link3[2]);
    linkcnt++;
  }
  if (link2sz != 0 && link3sz != 0 && ring3sz == 0 && ring4sz == 0) {
    ok = true;
    linkans[linkcnt].push_back(link2[0]);
    linkans[linkcnt].push_back(link3[0]);
    linkcnt++;
    linkans[linkcnt].push_back(link3[1]);
    linkans[linkcnt].push_back(link2[1]);
    linkans[linkcnt].push_back(link3[2]);
    linkcnt++;
  }
  if (link2sz == 0 && link3sz == 0 && ring3sz != 0 && ring4sz == 0) {
    if (free2.size() >= 2) {
      ok = true;
      int x = free2[0];
      int y = free2[1];
      linkans[linkcnt].push_back(ring3[0]);
      linkans[linkcnt].push_back(x);
      linkans[linkcnt].push_back(ring3[1]);
      linkcnt++;
      linkans[linkcnt].push_back(y);
      linkans[linkcnt].push_back(ring3[2]);
      linkcnt++;
    } else {
      if (free2.size() >= 1) {
        if (linkcnt > 0) {
          int x = free2[0];
          linkans[linkcnt].push_back(ring3[0]);
          linkans[linkcnt].push_back(x);
          linkans[linkcnt].push_back(ring3[1]);
          linkcnt++;
          linkans[0].push_back(ring3[2]);
          ok = true;
        } else {
          if (ringcnt > 0) {
            int x = free2[0];
            linkans[linkcnt].push_back(ring3[0]);
            linkans[linkcnt].push_back(x);
            linkans[linkcnt].push_back(ring3[1]);
            linkcnt++;
            ringans[0].push_back(ring3[2]);
            ok = true;
          }
        }
      } else {
        if (linkcnt > 0) {
          ok = true;
          int last = linkans[0].size();
          int x = linkans[0][last - 1];
          int y = linkans[0][last - 2];
          linkans[0].pop_back();
          linkans[0].pop_back();
          linkans[0].push_back(ring3[0]);
          linkans[0].push_back(x);
          linkans[0].push_back(ring3[1]);
          linkans[0].push_back(y);
          linkans[0].push_back(ring3[2]);
        } else {
          if (ringcnt > 0) {
            ok = true;
            int last = ringans[0].size();
            int x = ringans[0][last - 1];
            int y = ringans[0][last - 2];
            ringans[0].pop_back();
            ringans[0].pop_back();
            ringans[0].push_back(ring3[0]);
            ringans[0].push_back(x);
            ringans[0].push_back(ring3[1]);
            ringans[0].push_back(y);
            ringans[0].push_back(ring3[2]);
          }
        }
      }
    }
  }
  if (link2sz != 0 && link3sz == 0 && ring3sz != 0 && ring4sz == 0) {
    linkans[linkcnt].push_back(ring3[0]);
    linkans[linkcnt].push_back(link2[0]);
    linkans[linkcnt].push_back(ring3[1]);
    linkans[linkcnt].push_back(link2[1]);
    linkans[linkcnt].push_back(ring3[2]);
    linkcnt++;
    ok = true;
  }
  if (link2sz == 0 && link3sz != 0 && ring3sz != 0 && ring4sz == 0) {
    linkans[linkcnt].push_back(ring3[0]);
    linkans[linkcnt].push_back(link3[0]);
    linkans[linkcnt].push_back(ring3[1]);
    linkans[linkcnt].push_back(link3[1]);
    linkans[linkcnt].push_back(ring3[2]);
    linkans[linkcnt].push_back(link3[2]);
    linkcnt++;
    ok = true;
  }
  if (link2sz != 0 && link3sz != 0 && ring3sz != 0 && ring4sz == 0) {
    linkans[linkcnt].push_back(ring3[0]);
    linkans[linkcnt].push_back(link3[0]);
    linkans[linkcnt].push_back(ring3[1]);
    linkans[linkcnt].push_back(link3[1]);
    linkans[linkcnt].push_back(ring3[2]);
    linkans[linkcnt].push_back(link3[2]);
    linkans[linkcnt].push_back(link2[0]);
    linkcnt++;
    ok = true;
  }
  if (link2sz == 0 && link3sz == 0 && ring3sz == 0 && ring4sz != 0) {
    if (free2.size() >= 1) {
      int x = free2[0];
      linkans[linkcnt].push_back(ring4[0]);
      linkans[linkcnt].push_back(ring4[2]);
      linkans[linkcnt].push_back(x);
      linkans[linkcnt].push_back(ring4[1]);
      linkans[linkcnt].push_back(ring4[3]);
      linkcnt++;
      ok = true;
    } else {
      if (linkcnt > 0) {
        int x = linkans[0][linkans[0].size() - 1];
        linkans[0].pop_back();
        linkans[0].push_back(ring4[0]);
        linkans[0].push_back(ring4[2]);
        linkans[0].push_back(x);
        linkans[0].push_back(ring4[1]);
        linkans[0].push_back(ring4[3]);
        linkcnt++;
        ok = true;
      } else {
        if (ringcnt > 0) {
          int x = ringans[0][ringans[0].size() - 1];
          ringans[0].pop_back();
          ringans[0].push_back(ring4[0]);
          ringans[0].push_back(ring4[2]);
          ringans[0].push_back(x);
          ringans[0].push_back(ring4[1]);
          ringans[0].push_back(ring4[3]);
          ringcnt++;
          ok = true;
        }
      }
    }
  }
  if (link2sz != 0 && link3sz == 0 && ring3sz == 0 && ring4sz != 0) {
    ok = true;
    linkans[linkcnt].push_back(ring4[0]);
    linkans[linkcnt].push_back(ring4[2]);
    linkans[linkcnt].push_back(link2[1]);
    linkans[linkcnt].push_back(ring4[3]);
    linkans[linkcnt].push_back(ring4[1]);
    linkans[linkcnt].push_back(link2[0]);
    linkcnt++;
  }
  if (link2sz == 0 && link3sz != 0 && ring3sz == 0 && ring4sz != 0) {
    ok = true;
    linkans[linkcnt].push_back(ring4[0]);
    linkans[linkcnt].push_back(link3[0]);
    linkans[linkcnt].push_back(ring4[1]);
    linkans[linkcnt].push_back(link3[1]);
    linkans[linkcnt].push_back(ring4[2]);
    linkans[linkcnt].push_back(link3[2]);
    linkans[linkcnt].push_back(ring4[3]);
    linkcnt++;
  }
  if (link2sz != 0 && link3sz != 0 && ring3sz == 0 && ring4sz != 0) {
    ok = true;
    linkans[linkcnt].push_back(ring4[0]);
    linkans[linkcnt].push_back(link3[0]);
    linkans[linkcnt].push_back(ring4[1]);
    linkans[linkcnt].push_back(link3[1]);
    linkans[linkcnt].push_back(ring4[2]);
    linkans[linkcnt].push_back(link3[2]);
    linkans[linkcnt].push_back(ring4[3]);
    linkans[linkcnt].push_back(link2[0]);
    linkcnt++;
  }
  if (link2sz == 0 && link3sz == 0 && ring3sz != 0 && ring4sz != 0) {
    ok = true;
    ringans[ringcnt].push_back(ring4[0]);
    ringans[ringcnt].push_back(ring3[0]);
    ringans[ringcnt].push_back(ring4[1]);
    ringans[ringcnt].push_back(ring3[2]);
    ringans[ringcnt].push_back(ring4[3]);
    ringans[ringcnt].push_back(ring3[1]);
    ringans[ringcnt].push_back(ring4[2]);
    ringcnt++;
  }
  if (link2sz != 0 && link3sz == 0 && ring3sz != 0 && ring4sz != 0) {
    ok = true;
    ringans[ringcnt].push_back(ring4[0]);
    ringans[ringcnt].push_back(ring3[0]);
    ringans[ringcnt].push_back(ring4[1]);
    ringans[ringcnt].push_back(ring3[2]);
    ringans[ringcnt].push_back(ring4[3]);
    ringans[ringcnt].push_back(ring3[1]);
    ringans[ringcnt].push_back(ring4[2]);
    ringans[ringcnt].push_back(link2[0]);
    ringcnt++;
  }
  if (link2sz == 0 && link3sz != 0 && ring3sz != 0 && ring4sz != 0) {
    ok = true;
    ringans[ringcnt].push_back(ring4[0]);
    ringans[ringcnt].push_back(ring3[0]);
    ringans[ringcnt].push_back(ring4[1]);
    ringans[ringcnt].push_back(ring3[2]);
    ringans[ringcnt].push_back(ring4[3]);
    ringans[ringcnt].push_back(ring3[1]);
    ringans[ringcnt].push_back(ring4[2]);
    ringans[ringcnt].push_back(link3[1]);
    ringcnt++;
    linkans[linkcnt].push_back(link3[0]);
    linkans[linkcnt].push_back(link3[2]);
    linkcnt++;
  }
  if (link2sz != 0 && link3sz != 0 && ring3sz != 0 && ring4sz != 0) {
    ok = true;
    ringans[ringcnt].push_back(ring4[0]);
    ringans[ringcnt].push_back(ring3[0]);
    ringans[ringcnt].push_back(ring4[1]);
    ringans[ringcnt].push_back(ring3[2]);
    ringans[ringcnt].push_back(ring4[3]);
    ringans[ringcnt].push_back(ring3[1]);
    ringans[ringcnt].push_back(ring4[2]);
    ringans[ringcnt].push_back(link3[1]);
    ringcnt++;
    linkans[linkcnt].push_back(link2[0]);
    linkans[linkcnt].push_back(link3[0]);
    linkcnt++;
    linkans[linkcnt].push_back(link3[1]);
    linkans[linkcnt].push_back(link2[1]);
    linkans[linkcnt].push_back(link3[2]);
    linkcnt++;
  }
  if (!ok) {
    cout << -1 << endl;
  } else {
    for (int i = 0; i < linkcnt; i++) {
      int sz = linkans[i].size();
      for (int j = 0; j < sz - 1; j++) {
        cout << linkans[i][j] << " " << linkans[i][j + 1] << endl;
      }
    }
    for (int i = 0; i < ringcnt; i++) {
      int sz = ringans[i].size();
      for (int j = 0; j < sz - 1; j++) {
        cout << ringans[i][j] << " " << ringans[i][j + 1] << endl;
      }
      if (sz >= 3) {
        cout << ringans[i][sz - 1] << " " << ringans[i][0] << endl;
      }
    }
  }
  t_end = clock();
  return 0;
}