#include <bits/stdc++.h>
using namespace std;
const int maxn = 14, inf = 300;
bool path[maxn][maxn][1 << maxn], g[maxn][maxn];
int n, m, dp[1 << maxn], nxt[maxn][maxn][1 << maxn];
vector<pair<int, int> > cer[1 << maxn];
vector<pair<int, int> > extractPath(int v, int u, int mask) {
  assert(path[v][u][mask]);
  assert((mask >> v & 1) && (mask >> u & 1));
  vector<pair<int, int> > back;
  if (v == u)
    if (__builtin_popcount(mask) <= 1)
      return {};
    else
      back = extractPath(v, nxt[v][u][mask], mask);
  else
    back = extractPath(v, nxt[v][u][mask], mask ^ (1 << u));
  back.push_back({nxt[v][u][mask], u});
  return back;
}
bool smin(int &a, int b) {
  if (a > b) return a = b, 1;
  return 0;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int v, u;
    cin >> v >> u;
    v--, u--;
    g[v][u] = 1;
    g[u][v] = 1;
    path[v][u][(1 << v) | (1 << u)] = 1;
    nxt[v][u][(1 << v) | (1 << u)] = v;
  }
  for (int i = 0; i < n; i++) path[i][i][1 << i] = 1;
  for (int mask = 1; mask < 1 << n; mask++) {
    if (__builtin_popcount(mask) == 1) {
      dp[mask] = 0;
      continue;
    }
    dp[mask] = inf;
    vector<int> vers;
    for (int i = 0; i < n; i++)
      if (mask >> i & 1) vers.push_back(i);
    for (auto st : vers)
      for (auto en : vers)
        for (auto mid : vers)
          if (st != en && mid != st && g[mid][en] &&
              path[st][mid][mask ^ (1 << en)])
            path[st][en][mask] = 1, nxt[st][en][mask] = mid;
    for (auto st : vers)
      for (auto en : vers)
        for (auto mid : vers)
          if (st == en && g[mid][en] && path[st][mid][mask] &&
              nxt[st][mid][mask] != st)
            path[st][en][mask] = 1, nxt[st][en][mask] = mid;
    for (auto st : vers)
      for (auto en : vers) {
        int od = mask ^ ((1 << st) | (1 << en));
        for (int sub = od;; sub = (sub - 1) & od) {
          if (path[st][en][mask ^ sub] &&
              smin(dp[mask], dp[sub | (1 << st) | (1 << en)] +
                                 __builtin_popcount(mask ^ sub) - (st != en))) {
            auto tmp = extractPath(st, en, mask ^ sub);
            tmp.insert(tmp.end(), cer[sub | (1 << st) | (1 << en)].begin(),
                       cer[sub | (1 << st) | (1 << en)].end());
            cer[mask] = tmp;
          }
          if (!sub) break;
        }
      }
  }
  cout << dp[(1 << n) - 1] << '\n';
  for (auto [a, b] : cer[(1 << n) - 1]) cout << a + 1 << ' ' << b + 1 << '\n';
}
