#include <bits/stdc++.h>
using namespace std;
const int Maxn = 14;
const int INF = 0x3f3f3f3f;
int N, M;
vector<int> G[Maxn + 5];
void addedge(int u, int v) { G[u].push_back(v), G[v].push_back(u); }
int f[(1 << Maxn) + 5];
pair<int, int> last[(1 << Maxn) + 5];
int lasts[(1 << Maxn) + 5];
bool go[Maxn + 3][Maxn + 3][(1 << Maxn) + 3];
int lastnode[Maxn + 3][Maxn + 3][(1 << Maxn) + 3];
inline int lowbit(int x) { return x & (-x); }
inline int bitcount(int x) {
  int ret = 0;
  while (x) ret++, x -= lowbit(x);
  return ret;
}
int main() {
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= M; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    addedge(u, v);
  }
  memset(f, 0x3f, sizeof f);
  for (int u = 1; u <= N; u++)
    for (auto v : G[u]) go[u][v][0] = true, lastnode[u][v][0] = u;
  for (int s = 0; s < (1 << N); s++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++) {
        if ((s & (1 << (i - 1))) || (s & (1 << (j - 1))) || i == j ||
            !go[i][j][s])
          continue;
        for (auto k : G[j]) {
          if (s & (1 << (k - 1)) || k == i && s == 0) continue;
          int t = s ^ (1 << (j - 1));
          if (!go[i][k][t]) go[i][k][t] = true, lastnode[i][k][t] = j;
        }
      }
  f[1] = 0;
  for (int s = 0; s < (1 << N); s++)
    for (int t = s; t; t = (t - 1) & s) {
      int lst = s ^ t;
      int cnt = bitcount(t) + 1;
      if (f[lst] + cnt >= f[s]) continue;
      for (int u = 1; u <= N; u++) {
        if (!(lst & (1 << (u - 1)))) continue;
        for (int v = 1; v <= N; v++) {
          if (!(lst & (1 << (v - 1)))) continue;
          if (go[u][v][t]) {
            f[s] = f[lst] + cnt;
            last[s] = make_pair(u, v);
            lasts[s] = t;
          }
        }
      }
    }
  if (f[(1 << N) - 1] == INF) {
    puts("-1");
    return 0;
  }
  printf("%d\n", f[(1 << N) - 1]);
  int t = (1 << N) - 1;
  while (t != 1) {
    int lst = lasts[t];
    int x = last[t].first, y = last[t].second;
    t ^= lst;
    while (lst) {
      int z = lastnode[x][y][lst];
      printf("%d %d\n", y, z);
      lst ^= (1 << (z - 1));
      y = z;
    }
    printf("%d %d\n", x, y);
  }
  return 0;
}
