#include <bits/stdc++.h>
using namespace std;
const int maxn = (1 << 14) + 10;
const int inf = 1e8;
int n, m, bit[20], cnt[maxn], f[maxn], pa[maxn], push_back[maxn], pf[maxn],
    pre[maxn][20][20];
bool g[maxn][20][20], can[20][20];
vector<int> v[maxn];
void add(int x, int y) { can[x + 1][y + 1] = can[y + 1][x + 1] = true; }
void dfs(int mask, int a, int c) {
  if (a == c) {
    return;
  }
  int b = pre[mask][a][c];
  add(b, c);
  dfs(mask ^ (1 << c), a, b);
}
void get(int mask) {
  if (!f[mask]) {
    return;
  }
  int tmp = pf[mask];
  int a = pa[mask], b = push_back[mask];
  dfs(mask ^ tmp, a, b);
  add(a, v[tmp & bit[a]][0]);
  add(b, v[tmp & bit[b]].back());
  get(tmp);
}
int main() {
  scanf("%d%d", &n, &m);
  int u = (1 << n) - 1;
  for (int mask = 1; mask <= u; mask++) {
    for (int i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        v[mask].push_back(i);
        cnt[mask]++;
      }
    }
  }
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--;
    y--;
    bit[x] |= (1 << y);
    bit[y] |= (1 << x);
  }
  for (int i = 0; i <= u; i++) {
    f[i] = inf;
  }
  for (int i = 0; i < n; i++) {
    g[1 << i][i][i] = true;
    f[1 << i] = 0;
  }
  for (int mask = 1; mask <= u; mask++) {
    for (int i = 0, sz = (int)v[mask].size(); i < sz; i++) {
      int a = v[mask][i];
      for (int j = 0; j < sz; j++) {
        int b = v[mask][j];
        if (!g[mask][a][b]) {
          continue;
        }
        int s = (u ^ mask) & bit[b];
        for (int k = 0; k < v[s].size(); k++) {
          int c = v[s][k];
          g[mask | (1 << c)][a][c] = true;
          pre[mask | (1 << c)][a][c] = b;
        }
      }
    }
  }
  for (int mask = 1; mask <= u; mask++) {
    if (f[mask] >= inf) {
      continue;
    }
    for (int s = (u ^ mask); s; s = (s - 1) & (u ^ mask)) {
      for (int i = 0, sz = (int)v[s].size(); i < sz; i++) {
        int a = v[s][i];
        if (!(bit[a] & mask)) {
          continue;
        }
        for (int j = 0; j < sz; j++) {
          int b = v[s][j];
          if (!(bit[b] & mask)) {
            continue;
          }
          if (i == j && cnt[bit[a] & mask] < 2) {
            continue;
          }
          if (!g[s][a][b]) {
            continue;
          }
          if (f[mask] + cnt[s] + 1 < f[mask | s]) {
            int now = mask | s;
            f[now] = f[mask] + cnt[s] + 1;
            pa[now] = a;
            push_back[now] = b;
            pf[now] = mask;
          }
        }
      }
    }
  }
  get(u);
  printf("%d\n", f[u]);
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (can[i][j]) {
        printf("%d %d\n", i, j);
      }
    }
  }
  return 0;
}
