#include <bits/stdc++.h>
using namespace std;
int n, m, cnt, in[100005], isch[100005];
vector<int> adj[100005], comp[100005];
map<int, int> neis[100005];
void dfs(int v, int c) {
  int i;
  in[v] = c;
  comp[c].push_back(v);
  if ((int)adj[v].size() < 2) isch[c] = 1;
  for (i = 0; i < (int)adj[v].size(); ++i) {
    int u = adj[v][i];
    if (in[u] == -1) {
      dfs(u, c);
    }
  }
}
int gcd(int a, int b) {
  if (!a || !b) return a ? a : b;
  return gcd(b, a % b);
}
vector<vector<int> > dvsn[100005];
void append(vector<int> &V, vector<int> U) {
  int i;
  for (i = 0; i < (int)U.size(); ++i) V.push_back(U[i]);
}
void print(vector<int> vec) {
  int i;
  for (i = 0; i < m; ++i) {
    printf("%d %d\n", vec[i] + 1, vec[(i + 1) % (int)vec.size()] + 1);
  }
}
vector<int> cvs[4];
int main() {
  int i, j, k, l;
  scanf("%d%d", &n, &m);
  for (i = 0; i < m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u;
    --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
    neis[u][v] = neis[v][u] = 1;
  }
  memset(in, -1, sizeof(in));
  for (i = 0; i < n; ++i) {
    if (in[i] == -1 && (int)adj[i].size() == 1) dfs(i, cnt++);
  }
  for (i = 0; i < n; ++i) {
    if (in[i] == -1) dfs(i, cnt++);
  }
  int L = 0, mx = 1, Ld = -1;
  for (i = 0; i < cnt; ++i) {
    int S = (int)comp[i].size();
    if (S > L && !isch[i]) {
      Ld = i;
      L = S;
    }
    int cp, g;
    if (S < 4) {
      dvsn[i].resize(S);
      for (j = 0; j < S; ++j) dvsn[i][j].resize(1, comp[i][j]);
    } else {
      for (cp = 2; cp < S - 1; ++cp) {
        if (gcd(cp, S) == 1) break;
      }
      if (cp >= S - 1) cp = 2;
      g = gcd(cp, S);
      dvsn[i].resize(g);
      for (j = 0; j < g; ++j) {
        for (k = 0; k < S / g; ++k) {
          dvsn[i][j].push_back(comp[i][(k * cp + j) % S]);
        }
      }
    }
    mx = max(mx, (int)dvsn[i].size());
  }
  if (L >= 5 && !(L == 6 && cnt == 1)) {
    int ptr = 0, os = (int)dvsn[Ld].size();
    dvsn[Ld].resize(mx);
    for (i = os; i < mx; ++i) {
      while ((int)dvsn[Ld][ptr].size() == 1) ++ptr;
      dvsn[Ld][i].push_back(dvsn[Ld][ptr].back());
      dvsn[Ld][ptr].pop_back();
    }
    vector<int> sb;
    for (i = 0; i < mx; ++i) {
      for (j = 0; j < cnt; ++j) {
        if (j != Ld && i < (int)dvsn[j].size()) append(sb, dvsn[j][i]);
      }
      append(sb, dvsn[Ld][i]);
    }
    print(sb);
    return 0;
  }
  if (n <= 8) {
    int deg[n];
    vector<pair<int, int> > es;
    for (i = 0; i < n; ++i) {
      for (j = i + 1; j < n; ++j) {
        if (!neis[i].count(j)) es.push_back(make_pair(i, j));
      }
    }
    for (i = 0; i < (1 << (int)es.size()); ++i) {
      if (__builtin_popcount(i) != m) continue;
      memset(deg, 0, sizeof(deg));
      for (j = 0; j < (int)es.size(); ++j) {
        if (i & (1 << j)) {
          ++deg[es[j].first];
          ++deg[es[j].second];
        }
      }
      for (j = 0; j < n; ++j) {
        if (deg[j] > 2) break;
      }
      if (j == n) {
        for (j = 0; j < (int)es.size(); ++j) {
          if (i & (1 << j))
            printf("%d %d\n", es[j].first + 1, es[j].second + 1);
        }
        return 0;
      }
    }
    printf("-1\n");
    return 0;
  }
  const int COLITR = 200, RNDITR = 1000;
  srand(19260817);
  for (i = 0; i < COLITR; ++i) {
    while (1) {
      for (j = 0; j < 4; ++j) cvs[j].clear();
      for (j = 0; j < cnt; ++j) {
        int c = rand() % 4;
        for (k = 0; k < (int)comp[j].size(); ++k) {
          cvs[c].push_back(comp[j][k]);
          c = (c + 1) % 4;
        }
      }
      for (j = 0; j < 4; ++j) {
        if (cvs[j].empty()) break;
      }
      if (j == 4) break;
    }
    for (j = 0; j < RNDITR; ++j) {
      int d[4][2];
      for (k = 0; k < 4; ++k) {
        int S = (int)cvs[k].size();
        while (1) {
          int x = rand() % S, y = rand() % S;
          if (S == 1 || x != y) {
            d[k][0] = cvs[k][x];
            d[k][1] = cvs[k][y];
            break;
          }
        }
      }
      for (k = 0; k < 4; ++k) {
        if (neis[d[k][1]].count(d[(k + 1) % 4][0])) break;
      }
      if (k == 4) {
        vector<int> vec;
        for (k = 0; k < 4; ++k) {
          vec.push_back(d[k][0]);
          for (l = 0; l < (int)cvs[k].size(); ++l) {
            if (cvs[k][l] != d[k][0] && cvs[k][l] != d[k][1])
              vec.push_back(cvs[k][l]);
          }
          if (d[k][1] != d[k][0]) vec.push_back(d[k][1]);
        }
        print(vec);
        return 0;
      }
    }
  }
  printf("-1\n");
  return 0;
}
