#include <bits/stdc++.h>
using namespace std;
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(long long &x, long long y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(long long &x, long long y) { return (y > x) ? x = y, 1 : 0; }
const int N = 14;
const int inf = (int)1e9 + 1;
const long long big = (long long)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD2 = 998244353;
const double eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;
int dp[1 << N];
pair<pair<int, int>, int> come[1 << N];
bool g[N][N];
bool path[1 << N][N][N];
int come_path[1 << N][N][N];
int cnt_bits[1 << N];
vector<pair<int, int> > get_path(int mask, int s, int t) {
  mask |= (1 << s) | (1 << t);
  vector<pair<int, int> > res;
  while (s != t) {
    int pr = come_path[mask][s][t];
    res.push_back({pr, t});
    mask ^= (1 << t);
    t = pr;
  }
  reverse(res.begin(), res.end());
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.precision(20);
  cout << fixed;
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    g[u][v] = g[v][u] = true;
  }
  for (int i = 0; i < n; i++) {
    path[1 << i][i][i] = true;
  }
  for (int mask = 0; mask < (1 << n); mask++) {
    for (int s = 0; s < n; s++) {
      for (int t = 0; t < n; t++) {
        if (!path[mask][s][t]) {
          continue;
        }
        for (int nv = 0; nv < n; nv++) {
          if (!((mask >> nv) & 1) && g[t][nv]) {
            if (!path[mask | (1 << nv)][s][nv]) {
              path[mask | (1 << nv)][s][nv] = true;
              come_path[mask | (1 << nv)][s][nv] = t;
            }
          }
        }
      }
    }
  }
  for (int i = 0; i < (1 << n); i++) {
    cnt_bits[i] = __builtin_popcount(i);
  }
  fill(dp, dp + (1 << n), inf);
  for (int i = 0; i < n; i++) {
    dp[1 << i] = 0;
  }
  for (int mask = 0; mask < (1 << n); mask++) {
    if (dp[mask] == inf) {
      continue;
    }
    for (int s = 0; s < n; s++) {
      if (!((mask >> s) & 1)) {
        continue;
      }
      for (int t = 0; t < n; t++) {
        if (!((mask >> t) & 1)) {
          continue;
        }
        if (s == t) {
          continue;
        }
        int AV = ((1 << n) - 1) ^ mask;
        for (int sm = AV;; sm = (sm - 1) & AV) {
          if (!path[sm | (1 << s) | (1 << t)][s][t]) {
            if (!sm) {
              break;
            }
            continue;
          }
          if (setmin(dp[mask | sm], dp[mask] + cnt_bits[sm] + 1)) {
            come[mask | sm] = {{s, t}, sm};
          }
          if (!sm) {
            break;
          }
        }
      }
      for (int t = 0; t < n; t++) {
        if ((mask >> t) & 1) {
          continue;
        }
        assert(s != t);
        int AV = ((1 << n) - 1) ^ mask;
        for (int sm = AV;; sm = (sm - 1) & AV) {
          if (!((sm >> t) & 1)) {
            if (!sm) {
              break;
            }
            continue;
          }
          if (!path[sm | (1 << s) | (1 << t)][s][t]) {
            if (!sm) {
              break;
            }
            continue;
          }
          if (sm != (1 << t) && g[t][s]) {
            if (setmin(dp[mask | sm], dp[mask] + cnt_bits[sm] + 1)) {
              come[mask | sm] = {{s, n + t}, sm};
            }
          }
          if (!sm) {
            break;
          }
        }
      }
    }
  }
  cout << dp[(1 << n) - 1] << "\n";
  int mask = (1 << n) - 1;
  while (true) {
    auto p = come[mask];
    if (p.first.second >= n) {
      p.first.second -= n;
      cout << p.first.first + 1 << " " << p.first.second + 1 << "\n";
    }
    for (auto it : get_path(p.second, p.first.first, p.first.second)) {
      cout << it.first + 1 << " " << it.second + 1 << "\n";
    }
    mask ^= p.second;
    if (cnt_bits[mask] == 1) {
      break;
    }
  }
  return 0;
}
