#include <bits/stdc++.h>
using namespace std;
const int maxn = 14;
int dp[1 << maxn], n, m, ver[maxn][maxn][1 << maxn];
pair<pair<int, int>, int> pre[1 << maxn];
bool valid[maxn][maxn][1 << maxn];
vector<int> G[maxn];
int main() {
  scanf("%d%d", &n, &m);
  while (m--) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
  for (int(u) = (0); (u) <= ((n)-1); (u)++)
    for (int v : G[u]) valid[u][v][0] = true;
  for (int(mask) = (0); (mask) <= ((1 << n) - 1); (mask)++)
    for (int(i) = (0); (i) <= ((n)-1); (i)++)
      for (int(j) = (0); (j) <= ((n)-1); (j)++) {
        if (!valid[i][j][mask]) continue;
        for (int k : G[i])
          if (!(mask & (1 << k)) && !valid[k][j][mask | (1 << i)] &&
              (mask || k != j)) {
            ver[k][j][mask | (1 << i)] = i;
            valid[k][j][mask | (1 << i)] = true;
          }
      }
  memset(dp, 0x3f, sizeof(dp));
  for (int(mask) = (1); (mask) <= ((1 << n) - 1); (mask)++) {
    int cnt = __builtin_popcount(mask);
    if (cnt == 1) {
      dp[mask] = 0;
      pre[mask] = {{-1, -1}, 0};
      continue;
    }
    for (int sub = mask & (mask - 1); sub; sub = mask & (sub - 1)) {
      int rem = mask ^ sub, inc = __builtin_popcount(rem) + 1;
      for (int(i) = (0); (i) <= ((n)-1); (i)++)
        if (sub & (1 << i)) {
          for (int(j) = (0); (j) <= ((n)-1); (j)++)
            if (sub & (1 << j)) {
              if (valid[i][j][rem] && dp[sub] + inc < dp[mask]) {
                dp[mask] = dp[sub] + inc;
                pre[mask] = {{i, j}, rem};
              }
            }
        }
    }
  }
  printf("%d\n", dp[(1 << n) - 1]);
  for (int mask = (1 << n) - 1; __builtin_popcount(mask) > 1;) {
    int u = pre[mask].first.first, v = pre[mask].first.second,
        rem = pre[mask].second;
    for (int sub = rem; sub;) {
      int nxt = ver[u][v][sub];
      printf("%d %d\n", u + 1, nxt + 1);
      sub ^= 1 << nxt;
      u = nxt;
    }
    printf("%d %d\n", u + 1, v + 1);
    mask = mask ^ rem;
  }
}
