#include <bits/stdc++.h>
using namespace std;
const int INF = int(1E9);
int lg[1 << 14], bts[1 << 14];
int lowbit(int x) { return x & -x; }
int G[14], n, m, t;
bool f[14][1 << 14];
pair<int, int> pre1[14][1 << 14];
void get(const int a[], const int &n, const int &S) {
  int t = (1 << n);
  for (int i = 0; i < n; i++)
    for (int s = 0; s < t; s++) f[i][s] = false;
  int x, p, y, q;
  for (p = S, x = lg[lowbit(S)]; p; p ^= lowbit(p), x = lg[lowbit(p)])
    f[x][1 << x] = true;
  for (int s = 0; s < t; s++) {
    for (p = s, x = lg[lowbit(s)]; p; p ^= lowbit(p), x = lg[lowbit(p)]) {
      if (!f[x][s]) continue;
      for (q = a[x] & ((t - 1) ^ s), y = lg[lowbit(a[x] & ((t - 1) ^ s))]; q;
           q ^= lowbit(q), y = lg[lowbit(q)])
        f[y][s | (1 << y)] = true, pre1[y][s | (1 << y)] = make_pair(x, s);
    }
  }
}
int dp[1 << 14], pre2[1 << 14];
void update(int s1, int s2, int k) {
  if (dp[s1] > k) dp[s1] = k, pre2[s1] = s2;
}
int a[14], b[14];
void print(int S) {
  if (bts[S] == 1) return;
  int T = pre2[S], p, x;
  if (bts[S] - bts[T] == 1) {
    int q = lg[S ^ T], tot = 0;
    for (p = G[q] & T, x = lg[lowbit(G[q] & T)]; p;
         p ^= lowbit(p), x = lg[lowbit(p)]) {
      printf("%d %d\n", q + 1, x + 1), tot++;
      if (tot == 2) break;
    }
  } else {
    int s1 = 0, s2 = 0, cnt = 0;
    for (p = (t - 1) ^ T, x = lg[lowbit((t - 1) ^ T)]; p;
         p ^= lowbit(p), x = lg[lowbit(p)])
      b[cnt] = 0, a[cnt++] = x;
    for (int i = 0; i < cnt; i++)
      for (int j = 0; j < cnt; j++)
        if ((G[a[i]] >> a[j]) & 1) b[i] |= (1 << j);
    for (p = T, x = lg[lowbit(T)]; p; p ^= lowbit(p), x = lg[lowbit(p)])
      s1 |= G[x];
    for (int i = 0; i < cnt; i++)
      if ((s1 >> a[i]) & 1) s2 |= (1 << i);
    get(b, cnt, s2);
    int s3 = 0;
    for (int i = 0; i < cnt; i++)
      if ((S >> a[i]) & 1) s3 |= (1 << i);
    for (p = s2 & s3, x = lg[lowbit(s2 & s3)]; p;
         p ^= lowbit(p), x = lg[lowbit(p)]) {
      if (f[x][s3]) {
        printf("%d %d\n", lg[lowbit(T & G[a[x]])] + 1, a[x] + 1);
        pair<int, int> p = make_pair(x, s3);
        while ((1 << p.first) != p.second) {
          pair<int, int> q = pre1[p.first][p.second];
          printf("%d %d\n", a[p.first] + 1, a[q.first] + 1);
          p = q;
        }
        printf("%d %d\n", a[p.first] + 1, lg[lowbit(T & G[a[p.first]])] + 1);
        break;
      }
    }
  }
  print(T);
}
int main() {
  scanf("%d%d", &n, &m), t = (1 << n);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v), u--, v--;
    G[u] |= (1 << v), G[v] |= (1 << u);
  }
  for (int s = 1; s < t; s++) dp[s] = INF, bts[s] = bts[s >> 1] + (s & 1);
  for (int i = 0; i < n; i++) lg[1 << i] = i, dp[1 << i] = 0;
  for (int s = 1; s < t; s++) {
    if (dp[s] == INF) continue;
    int p, x, s1 = 0, s2 = 0, cnt = 0;
    for (p = (t - 1) ^ s, x = lg[lowbit((t - 1) ^ s)]; p;
         p ^= lowbit(p), x = lg[lowbit(p)])
      b[cnt] = 0, a[cnt++] = x;
    for (int i = 0; i < cnt; i++)
      if (bts[s & G[a[i]]] > 1) update(s | (1 << a[i]), s, dp[s] + 2);
    for (int i = 0; i < cnt; i++)
      for (int j = 0; j < cnt; j++)
        if ((G[a[i]] >> a[j]) & 1) b[i] |= (1 << j);
    for (p = s, x = lg[lowbit(s)]; p; p ^= lowbit(p), x = lg[lowbit(p)])
      s1 |= G[x];
    for (int i = 0; i < cnt; i++)
      if ((s1 >> a[i]) & 1) s2 |= (1 << i);
    get(b, cnt, s2);
    int t3 = (1 << cnt);
    for (int s3 = 0; s3 < t3; s3++) {
      if (bts[s3] < 2) continue;
      int s4 = 0;
      for (p = s3, x = lg[lowbit(s3)]; p; p ^= lowbit(p), x = lg[lowbit(p)])
        s4 |= (1 << a[x]);
      for (p = s2 & s3, x = lg[lowbit(s2 & s3)]; p;
           p ^= lowbit(p), x = lg[lowbit(p)]) {
        if (f[x][s3]) update(s | s4, s, dp[s] + bts[s4] + 1);
      }
    }
  }
  printf("%d\n", dp[t - 1]), print(t - 1);
}
