#include <bits/stdc++.h>
using namespace std;
const int maxn = 15, MASK = (1 << 14) + 10;
bool path[maxn][maxn][MASK], adj[maxn][maxn];
int dp[MASK], n;
pair<int, pair<int, int> > bef[MASK];
vector<pair<int, int> > ans;
void Add(int msk, int a, int b) {
  if (__builtin_popcount(msk) == 1) {
    int x = __builtin_ctz(msk);
    ans.push_back({x, a});
    ans.push_back({x, b});
    return;
  }
  for (int k = 0; k < n; k++) {
    if ((((msk) >> (k)) & 1) && adj[k][b] && path[a][k][msk ^ (1 << k)]) {
      ans.push_back({k, b});
      Add(msk ^ (1 << k), a, k);
      return;
    }
  }
  assert(0);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    adj[a][b] = adj[b][a] = 1;
  }
  for (int msk = 1; msk < (1 << n); msk++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (__builtin_popcount(msk) == 1) {
          int x = __builtin_ctz(msk);
          path[i][j][msk] = (i != j && adj[x][i] && adj[x][j]);
          continue;
        }
        if ((((msk) >> (i)) & 1) || (((msk) >> (j)) & 1)) continue;
        for (int k = 0; k < n; k++) {
          path[i][j][msk] |=
              (((msk) >> (k)) & 1) && adj[k][j] && path[i][k][msk ^ (1 << k)];
        }
      }
    }
  }
  for (int msk = 1; msk < (1 << n); msk++) {
    if (__builtin_popcount(msk) == 1) continue;
    dp[msk] = m + 10;
    for (int msk2 = (msk - 1) & msk; msk2 != 0; msk2 = (msk2 - 1) & msk) {
      int msk3 = msk ^ msk2;
      for (int i = 0; i < n; i++) {
        if ((((msk3) >> (i)) & 1) == 0) continue;
        for (int j = 0; j < n; j++) {
          if ((((msk3) >> (j)) & 1) == 0) continue;
          int num = __builtin_popcount(msk2);
          if (path[i][j][msk2] && dp[msk] > dp[msk3] + num + 1)
            bef[msk] = {msk2, {i, j}}, dp[msk] = dp[msk3] + num + 1;
        }
      }
    }
  }
  int msk = (1 << n) - 1;
  while (__builtin_popcount(msk) > 1) {
    Add(bef[msk].first, bef[msk].second.first, bef[msk].second.second);
    msk ^= bef[msk].first;
  }
  assert(dp[(1 << n) - 1] == int((ans).size()));
  cout << int((ans).size()) << "\n";
  for (pair<int, int> p : ans) {
    cout << p.first + 1 << " " << p.second + 1 << "\n";
  }
  return 0;
  ;
}
