#include <bits/stdc++.h>
using namespace std;
int pct(int x) { return __builtin_popcount(x); }
int pct(long long x) { return __builtin_popcountll(x); }
int bit(int x) { return 31 - __builtin_clz(x); }
int bit(long long x) { return 63 - __builtin_clzll(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
long long cdiv(long long a, long long b) {
  return a / b + !(a < 0 || a % b == 0);
}
template <typename T>
void leftShift(vector<T> &v, long long k) {
  k %= (int)v.size();
  if (k < 0) k += (int)v.size();
  rotate(v.begin(), v.begin() + k, v.end());
}
template <typename T>
void rightShift(vector<T> &v, long long k) {
  leftShift(v, (int)v.size() - k);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
  uniform_int_distribution<long long> uid(l, r);
  return uid(rng);
}
void pr() {}
void sc() {}
template <typename Head, typename... Tail>
void pr(Head H, Tail... T) {
  cout << H << " ";
  pr(T...);
}
template <typename Head, typename... Tail>
void sc(Head &H, Tail &...T) {
  cin >> H;
  sc(T...);
}
string to_string(__int128 x) {
  string s = "";
  bool neg = 0;
  if (x < 0) {
    s += "-";
    neg = 1;
    x = -x;
  }
  if (!x) s += '0';
  while (x) {
    int rem = x % 10;
    s += to_string(rem);
    x /= 10;
  }
  reverse(s.begin() + neg, s.end());
  return s;
}
const int mod = 1e9 + 7;
int pwr(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * 1LL * a) % mod;
    a = (a * 1LL * a) % mod;
    b >>= 1;
  }
  return ans;
}
vector<int> set_bits(int mask) {
  vector<int> v;
  int c = bit(mask);
  for (int i = 0; i <= c; i++) {
    if ((mask >> i) & 1) {
      v.push_back(i + 1);
    }
  }
  return v;
}
int get_bits(vector<int> bits) {
  int mask = 0;
  for (int b : bits) {
    mask ^= (1 << (b - 1));
  }
  return mask;
}
const int N = 15;
vector<int> g[N];
bool path[1 << N][N][N];
int par[1 << N][N][N];
bool path2[N][N][1 << N];
int par2[N][N][1 << N];
bool adj[N][N];
int dp[1 << N];
array<int, 4> par_dp[1 << N];
void gen(int i, int j, int mask) {
  42;
  while (pct(mask) != 1) {
    int k = par2[i][j][mask];
    pr(k + 1, j + 1);
    cout << '\n';
    if (j != i) mask ^= (1 << j);
    j = k;
  }
}
void solve() {
  int n, m;
  sc(n, m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    sc(u, v);
    u--, v--;
    adj[u][v] = adj[v][u] = 1;
  }
  int tot = (1 << n) - 1;
  for (int i = 0; i <= n - 1; i++) {
    memset(path, 0, sizeof path);
    path[1 << i][i][i] = 1;
    for (int mask = 0; mask <= tot; mask++) {
      for (int j = 0; j <= n - 1; j++) {
        for (int k = 0; k <= n - 1; k++) {
          if (!path[mask][j][k]) continue;
          if (!path2[i][k][mask]) {
            path2[i][k][mask] = 1;
            par2[i][k][mask] = j;
            if (adj[k][i] && j != i) {
              path2[i][i][mask] = 1;
              par2[i][i][mask] = k;
            }
          }
          int cmask = tot ^ mask;
          while (cmask) {
            int l = bit(cmask);
            cmask ^= (1 << l);
            if (j == l) continue;
            if (adj[k][l] && !((mask >> l) & 1)) {
              path[mask ^ (1 << l)][k][l] = 1;
              par[mask ^ (1 << l)][k][l] = j;
            }
          }
        }
      }
    }
  }
  for (int i = 0; i <= tot; i++) {
    dp[i] = 1e9;
  }
  dp[1] = 0;
  for (int mask = 0; mask <= tot; mask++) {
    if (dp[mask] == 1e9) continue;
    for (int i = 0; i <= n - 1; i++) {
      if (!((mask >> i) & 1)) continue;
      for (int j = 0; j <= n - 1; j++) {
        if (!((mask >> j) & 1)) continue;
        int cmask = tot ^ mask ^ ((1 << i) | (1 << j));
        int mmask = cmask;
        while (mmask > 0) {
          if (((mmask >> i) & 1) && ((mmask >> j) & 1) && path2[i][j][mmask]) {
            int val = dp[mask] + pct(mmask) - 1 + (i == j);
            int nmask = mask | mmask;
            if (dp[nmask] > val) {
              dp[nmask] = val;
              par_dp[nmask] = {mask, mmask, i, j};
            }
          }
          mmask = (mmask - 1) & cmask;
        }
      }
    }
  }
  cout << dp[tot] << '\n';
  while (tot != 1) {
    int path_mask = par_dp[tot][1];
    int i = par_dp[tot][2];
    int j = par_dp[tot][3];
    tot = par_dp[tot][0];
    gen(i, j, path_mask);
  }
}
signed main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  t = 1;
  for (int tt = 1; tt <= t; tt++) {
    solve();
  }
  return 0;
}
