#include <bits/stdc++.h>
using namespace std;
const int N = 14;
int read() {
  int s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * f;
}
void put(int x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) put(x / 10);
  putchar(x % 10 + '0');
}
struct edge {
  int x, y;
} e[N * N];
int len;
struct pre {
  int x, y, S;
} lst1[N + 1][N + 1][1 << N], lst2[1 << N];
int bin[N + 1], f[N + 1][N + 1][1 << N], d[N + 1][N + 1], g[1 << N],
    one[1 << N], num[1 << N];
int ct1[N + 1][1 << N], ct2[N + 1][1 << N];
void dfs2(int x, int y, int S) {
  if (one[S] == 1) return;
  int xx = lst1[x][y][S].x, yy = lst1[x][y][S].y, SS = lst1[x][y][S].S;
  if (xx == x)
    e[++len] = edge{y, yy};
  else
    e[++len] = edge{x, xx};
  dfs2(xx, yy, SS);
}
void dfs1(int S) {
  if (one[S] == 1) return;
  int xx = lst2[S].x, yy = lst2[S].y, SS = lst2[S].S;
  dfs2(xx, yy, S ^ SS);
  if (xx == yy) {
    e[++len] = edge{xx, ct1[xx][SS]};
    e[++len] = edge{yy, ct2[yy][SS]};
  } else {
    e[++len] = edge{xx, ct1[xx][SS]};
    e[++len] = edge{yy, ct1[yy][SS]};
  }
  dfs1(SS);
}
int main() {
  int n = read(), m = read();
  memset(d, 0, sizeof(d));
  bin[0] = 1;
  for (int i = 1; i <= n; i++) bin[i] = bin[i - 1] << 1;
  for (int i = 0; i < n; i++) num[bin[i]] = i + 1;
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    d[x][y] = d[y][x] = 1;
  }
  memset(f, 0, sizeof(f));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < bin[n]; j++)
      if (!(bin[i - 1] & j)) {
        for (int k = 1; k <= n; k++)
          if ((bin[k - 1] & j) && d[i][k]) {
            if (!ct1[i][j])
              ct1[i][j] = k;
            else
              ct2[i][j] = k;
          }
      }
  }
  for (int i = 1; i <= n; i++) f[i][i][bin[i - 1]] = 1;
  for (int i = 1; i < bin[n]; i++) {
    one[i] = one[i >> 1] + (i & 1);
    for (int x = 1; x <= n; x++)
      if (i & bin[x - 1]) {
        for (int y = 1; y <= n; y++)
          if ((i & bin[y - 1]) && f[x][y][i]) {
            for (int k = 1; k <= n; k++)
              if (!(i & bin[k - 1])) {
                if (d[x][k]) {
                  f[k][y][i | bin[k - 1]] = 1;
                  lst1[k][y][i | bin[k - 1]] = pre{x, y, i};
                }
                if (d[y][k]) {
                  f[x][k][i | bin[k - 1]] = 1;
                  lst1[x][k][i | bin[k - 1]] = pre{x, y, i};
                }
              }
          }
      }
  }
  memset(g, 63, sizeof(g));
  for (int i = 1; i <= n; i++) g[bin[i - 1]] = 0;
  for (int i = 1; i < bin[n]; i++) {
    for (int x = 1; x <= n; x++)
      if (ct1[x][i]) {
        for (int y = 1; y <= n; y++)
          if (x != y && ct1[y][i]) {
            int S = (bin[n] - 1) ^ i;
            for (int j = S; j; j = (j - 1) & S) {
              if (f[x][y][j] && one[j] + g[i] + 1 < g[i | j]) {
                g[i | j] = one[j] + g[i] + 1;
                lst2[i | j] = pre{x, y, i};
              }
            }
          }
      }
    for (int x = 1; x <= n; x++)
      if (ct1[x][i] && ct2[x][i]) {
        if (g[i] + 2 < g[i | bin[x - 1]]) {
          g[i | bin[x - 1]] = g[i] + 2;
          lst2[i | bin[x - 1]] = pre{x, x, i};
        }
      }
  }
  put(g[bin[n] - 1]), puts("");
  dfs1(bin[n] - 1);
  for (int i = 1; i <= len; i++)
    put(e[i].x), putchar(' '), put(e[i].y), puts("");
  return 0;
}
