#include <bits/stdc++.h>
using namespace std;
const int maxn = 16;
const int maxm = 17000;
const int maxs = 26;
const int inf = 1 << 28;
const int P = 1000000007;
const double error = 1e-9;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch <= 47 || ch >= 58) f = (ch == 45 ? -1 : 1), ch = getchar();
  while (ch >= 48 && ch <= 57) x = x * 10 + ch - 48, ch = getchar();
  return x * f;
}
struct edge {
  int u, v, w, next;
} e[maxm];
int n, m, cnt, head[maxn], bin[maxn], f[maxm], g[maxm][maxn][maxn],
    h[maxm][maxn][2];
pair<int, int> H[maxm][maxn][2], G[maxm][maxn][maxn];
struct rua {
  int pre, s, u, v;
  pair<int, int> a, b;
} F[maxm];
void insert(int u, int v, int w) {
  e[cnt] = (edge){u, v, w, head[u]}, head[u] = cnt++;
  e[cnt] = (edge){v, u, w, head[v]}, head[v] = cnt++;
}
int fac(int x) {
  int ans = 1;
  for (x = x & (x - 1); x; x = x & (x - 1)) ans++;
  return ans;
}
void init() {
  for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= n; k++) g[i][j][k] = inf;
  for (int i = 1; i <= n; i++) {
    bin[i] = 1 << (i - 1);
    g[bin[i]][i][i] = 0;
  }
  for (int i = 0; i < cnt; i++) {
    int u = e[i].u, v = e[i].v, s = bin[u] + bin[v];
    if (g[s][u][v] > e[i].w) {
      g[s][u][v] = e[i].w;
      G[s][u][v] = make_pair(-1, -1);
    }
  }
  for (int i = 1; i < (1 << n); i++)
    for (int u = 1; u <= n; u++)
      for (int v = 1; v <= n; v++)
        if ((bin[u] | i) == i && (bin[v] | i) == i)
          for (int k = head[v]; k != -1; k = e[k].next) {
            int fv = e[k].v;
            if ((bin[fv] | i) != i) {
              int s = i + bin[fv];
              if (g[s][u][fv] > g[i][u][v] + e[k].w) {
                g[s][u][fv] = g[i][u][v] + e[k].w;
                G[s][u][fv] = make_pair(i, v);
              }
            }
          }
  for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= 1; k++)
        h[i][j][k] = inf, H[i][j][k] = make_pair(0, 0);
  for (int i = 1; i < (1 << n); i++)
    for (int u = 1; u <= n; u++)
      if ((bin[u] | i) != i)
        for (int j = head[u]; j != -1; j = e[j].next) {
          int v = e[j].v;
          if ((bin[v] | i) == i) {
            if (e[j].w < h[i][u][0]) {
              h[i][u][1] = h[i][u][0];
              H[i][u][1] = H[i][u][0];
              h[i][u][0] = e[j].w;
              H[i][u][0] = make_pair(e[j].u, e[j].v);
            } else if (e[j].w < h[i][u][1])
              h[i][u][1] = e[j].w;
            H[i][u][1] = make_pair(e[j].u, e[j].v);
          }
        }
}
void work() {
  for (int i = 1; i < (1 << n); i++) f[i] = inf;
  for (int i = 1; i <= n; i++) f[bin[i]] = 0;
  for (int i = 1; i < (1 << n); i++)
    if (fac(i) >= 2)
      for (int s = i & (i - 1); s; s = (s - 1) & i) {
        int t = i - s;
        for (int u = 1; u <= n; u++)
          for (int v = 1; v <= n; v++)
            if ((bin[u] | s) == s && (bin[v] | s) == s) {
              if (u == v) {
                if (f[i] > f[t] + g[s][u][u] + h[t][u][0] + h[t][u][1]) {
                  f[i] = f[t] + g[s][u][u] + h[t][u][0] + h[t][u][1];
                  F[i].s = s;
                  F[i].pre = t;
                  F[i].u = F[i].v = u;
                  F[i].a = H[t][u][0];
                  F[i].b = H[t][u][1];
                }
              } else {
                if (f[i] > f[t] + g[s][u][v] + h[t][u][0] + h[t][v][0]) {
                  f[i] = f[t] + g[s][u][v] + h[t][u][0] + h[t][v][0];
                  F[i].s = s;
                  F[i].pre = t;
                  F[i].u = u, F[i].v = v;
                  F[i].a = H[t][u][0];
                  F[i].b = H[t][v][0];
                }
              }
            }
      }
}
void print_G(int s, int u, int v) {
  if (u == v) return;
  if (G[s][u][v] == make_pair(-1, -1)) {
    printf("%d %d\n", u, v);
    return;
  }
  printf("%d %d\n", G[s][u][v].second, v);
  print_G(G[s][u][v].first, u, G[s][u][v].second);
}
void print_F(int cur) {
  if (cur == 0) return;
  if (F[cur].a != make_pair(0, 0))
    printf("%d %d\n", F[cur].a.first, F[cur].a.second);
  if (F[cur].b != make_pair(0, 0))
    printf("%d %d\n", F[cur].b.first, F[cur].b.second);
  print_G(F[cur].s, F[cur].u, F[cur].v);
  print_F(F[cur].pre);
}
int main() {
  int t = 1;
  while (t--) {
    n = read(), m = read();
    memset(head, -1, sizeof head);
    cnt = 0;
    for (int i = 1; i <= m; i++) {
      int u = read(), v = read(), w = 1;
      insert(u, v, w);
    }
    init(), work();
    printf("%d\n", f[(1 << n) - 1]);
    print_F((1 << n) - 1);
  }
  return 0;
}
