#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
const int maxm = 20010;
int n, m;
int ct[maxm];
int dp[maxn][maxn][maxm];
int a[maxm], b[maxm], c[maxm];
vector<int> G[maxn];
void dfs(int x, int zt, int st) {
  if (x == st && zt) return;
  for (auto to : G[x]) {
    if ((1 << (to - 1)) & zt) continue;
    if (ct[zt] == 1 && to == st) continue;
    if (dp[st][to][zt]) continue;
    dp[st][to][zt] = 1;
    dfs(to, (1 << (to - 1)) | zt, st);
  }
}
vector<pair<int, int> > ans;
void dfs2(int x, int y, int z) {
  if (!z) {
    ans.push_back(make_pair(x, y));
    return;
  }
  int i, t;
  for (auto to : G[x]) {
    if (!((1 << (to - 1)) & z)) continue;
    if (!dp[to][y][(1 << (to - 1)) ^ z]) continue;
    ans.push_back(make_pair(x, to));
    dfs2(to, y, z ^ (1 << (to - 1)));
    return;
  }
}
int stane[maxm];
int main() {
  memset(stane, 0x3f, sizeof stane);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  for (int i = 1; i < (1 << n); i++) ct[i] = ct[i ^ (i & (-i))] + 1;
  for (int i = 1; i <= n; i++) dfs(i, 0, i);
  for (int i = 0; i < n; i++) stane[1 << i] = 0;
  for (int i = 1; i < (1 << n); i++) {
    for (int p = 1; p <= n; p++) {
      if (!((1 << (p - 1)) & i)) continue;
      for (int q = p; q <= n; q++) {
        if (!((1 << (q - 1)) & i)) continue;
        int t = ((1 << n) - 1) ^ i;
        for (int j = t; j; j = (j - 1) & t) {
          if (!dp[p][q][j]) continue;
          if (stane[i] + ct[j] + 1 < stane[i | j]) {
            stane[i | j] = stane[i] + ct[j] + 1;
            a[i | j] = p, b[i | j] = q, c[i | j] = j;
          }
        }
      }
    }
  }
  for (int i = (1 << n) - 1; ct[i] > 1; i = i ^ c[i]) dfs2(a[i], b[i], c[i]);
  cout << ans.size() << endl;
  for (auto x : ans) cout << x.first << ' ' << x.second << endl;
  return 0;
}
