#include <bits/stdc++.h>
using namespace std;
const int MAXN = 40000;
const int MAXM = 20000000;
const int INF = 100000;
int n, m;
int x[25][25];
int h[MAXN][20][2], g[MAXN][20][20], f[MAXN], ans1[MAXN][3], ans2[MAXN][20][2],
    ans3[MAXN][20][20];
int cnt(int a) {
  int ret = 0;
  for (int i = 1; i <= n; i++) {
    if (a & (1 << (i - 1))) ret++;
  }
  return ret;
}
void dfs2(int s, int i, int j) {
  if (cnt(s) == 2) {
    cout << i << ' ' << j << endl;
    return;
  }
  if (i == j) return;
  int k = ans3[s][i][j];
  cout << j << ' ' << k << endl;
  dfs2(s - (1 << (j - 1)), i, k);
}
void dfs1(int s) {
  if (cnt(s) <= 2) return;
  int u = ans1[s][0];
  int t = s - u;
  int i = ans1[s][1];
  int j = ans1[s][2];
  dfs2(t, i, j);
  if (i == j) {
    cout << i << ' ' << ans2[u][i][0] << endl;
    cout << j << ' ' << ans2[u][j][1] << endl;
  } else {
    cout << i << ' ' << ans2[u][i][0] << endl;
    cout << j << ' ' << ans2[u][j][0] << endl;
  }
  dfs1(u);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) x[i][j] = INF;
  for (int s = 0; s < (1 << n); s++) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) g[s][i][j] = INF;
  }
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    x[a][b] = x[b][a] = 1;
    g[(1 << (a - 1)) + (1 << (b - 1))][a][b] = 1;
    g[(1 << (a - 1)) + (1 << (b - 1))][b][a] = 1;
  }
  for (int i = 1; i <= n; i++) {
    g[1 << (i - 1)][i][i] = 0;
  }
  for (int s = 0; s < (1 << n); s++) {
    for (int i = 1; i <= n; i++) {
      if (!(s & (1 << (i - 1)))) continue;
      for (int j = 1; j <= n; j++) {
        if (!(s & (1 << (j - 1)))) continue;
        if (i == j && cnt(s) != 1) continue;
        for (int k = 1; k <= n; k++) {
          if (s & (1 << (k - 1))) continue;
          if (x[j][k] == 0) continue;
          if (g[s][i][j] + x[j][k] < g[s | (1 << (k - 1))][i][k]) {
            g[s | (1 << (k - 1))][i][k] = g[s][i][j] + 1;
            ans3[s | (1 << (k - 1))][i][k] = j;
          }
        }
      }
    }
  }
  for (int s = 0; s < (1 << n); s++) {
    for (int i = 1; i <= n; i++) {
      if (s & (1 << (i - 1))) continue;
      h[s][i][0] = h[s][i][1] = INF;
      for (int j = 1; j <= n; j++) {
        if (!(s & (1 << (j - 1)))) continue;
        if (x[i][j] <= h[s][i][0]) {
          if (x[i][j] < h[s][i][0]) {
            h[s][i][1] = h[s][i][0];
            ans2[s][i][1] = ans2[s][i][0];
            h[s][i][0] = x[i][j];
            ans2[s][i][0] = j;
          } else {
            h[s][i][1] = x[i][j];
            ans2[s][i][1] = j;
          }
        }
      }
    }
  }
  for (int s = 0; s < (1 << n); s++) f[s] = INF;
  for (int i = 1; i <= n; i++) f[1 << (i - 1)] = 0;
  for (int s = 0; s < (1 << n); s++) {
    if (cnt(s) <= 2) continue;
    for (int t = s & (s - 1); t; t = (t - 1) & s) {
      int u = s - t;
      for (int i = 1; i <= n; i++) {
        if (!(t & (1 << (i - 1)))) continue;
        for (int j = 1; j <= n; j++) {
          if (!(t & (1 << (j - 1)))) continue;
          if (i == j) {
            if (cnt(t) == 1 &&
                f[u] + g[t][i][j] + h[u][i][0] + h[u][j][1] < f[s]) {
              f[s] = f[u] + g[t][i][j] + h[u][i][0] + h[u][j][1];
              ans1[s][0] = u;
              ans1[s][1] = i;
              ans1[s][2] = j;
            }
          } else {
            if (f[u] + g[t][i][j] + h[u][i][0] + h[u][j][0] < f[s]) {
              f[s] = f[u] + g[t][i][j] + h[u][i][0] + h[u][j][0];
              ans1[s][0] = u;
              ans1[s][1] = i;
              ans1[s][2] = j;
            }
          }
        }
      }
    }
  }
  cout << f[(1 << n) - 1] << endl;
  dfs1((1 << n) - 1);
  return 0;
}
