#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
const int maxn = 1e5 + 10, maxm = 1e3 + 10, lg = 14, mod = 1e9 + 7, inf = 1e18;
const int M = (1 << lg) + 20;
int n, m;
bool g[lg][lg][M];
int pg[lg][lg][M];
int dp[M];
tuple<int, int, int> par[M];
void gans(int msk = (1 << n) - 1) {
  if (msk == 1) return;
  int x, y, ssk;
  tie(x, y, ssk) = par[msk];
  msk ^= ssk;
  while (ssk) {
    int xx = pg[x][y][ssk];
    cout << x + 1 << ' ' << xx + 1 << endl;
    ssk ^= (1 << xx);
    x = xx;
  }
  cout << x + 1 << ' ' << y + 1 << endl;
  return gans(msk);
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  while (m--) {
    int v, u;
    cin >> v >> u;
    v--, u--;
    g[v][u][0] = g[u][v][0] = 1;
  }
  for (int msk = 1; msk < (1 << n); msk++)
    for (int x = 0; x < n; x++)
      if ((msk >> x & 1) == 0)
        for (int y = 0; y < n; y++)
          if ((msk >> y & 1) == 0)
            if (x != y || (__builtin_popcount(msk)) > 1)
              for (int i = 0; i < n; i++)
                if (i != x && msk >> i & 1)
                  if (g[x][i][0] && g[i][y][msk ^ (1 << i)]) {
                    g[x][y][msk] = 1;
                    pg[x][y][msk] = i;
                    break;
                  }
  memset(dp, 69, sizeof(dp));
  dp[1] = 0;
  for (int msk = 1; msk < (1 << n) - 1; msk++)
    if (msk & 1) {
      int nsk = ((1 << n) - 1) ^ msk;
      for (int x = 0; x < n; x++)
        if (msk >> x & 1)
          for (int y = 0; y < n; y++)
            if (msk >> y & 1)
              for (int ssk = nsk; ssk; ssk = (ssk - 1) & nsk) {
                int ez = dp[msk] + (__builtin_popcount(ssk)) + 1;
                if (g[x][y][ssk] && dp[msk | ssk] > ez) {
                  dp[msk | ssk] = ez;
                  par[msk | ssk] = make_tuple(x, y, ssk);
                }
              }
    }
  cout << dp[(1 << n) - 1] << endl;
  gans();
  return 0;
}
