#include <bits/stdc++.h>
using namespace std;
const int MAXN = 14;
int n, m;
bool edges[MAXN][MAXN];
int hasPath[MAXN][MAXN][1 << MAXN];
int dp[1 << MAXN];
tuple<int, int, int> from[1 << MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  while (m--) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    edges[u][v] = edges[v][u] = true;
  }
  memset(hasPath, -1, sizeof(hasPath));
  for (int u = 0; u < n; ++u) {
    for (int v = 0; v < n; ++v) {
      if (u != v && edges[u][v]) {
        hasPath[u][v][0] = u;
      }
    }
  }
  for (int mask = 0; mask < (1 << n); ++mask) {
    for (int u = 0; u < n; ++u) {
      if (mask & (1 << u)) {
        continue;
      }
      for (int v = 0; v < n; ++v) {
        if ((mask & (1 << v)) || u == v || hasPath[u][v][mask] == -1) {
          continue;
        }
        for (int k = 0; k < n; ++k) {
          if (!edges[v][k] || (mask & (1 << k)) || k == hasPath[u][v][mask]) {
            continue;
          }
          int nextMask = mask | (1 << v);
          if (hasPath[u][k][nextMask] == -1) {
            hasPath[u][k][nextMask] = v;
          }
        }
      }
    }
  }
  memset(dp, -1, sizeof(dp));
  dp[1] = 0;
  for (int mask = 0; mask < (1 << n); ++mask) {
    for (int addMask = mask; addMask > 0; addMask = (addMask - 1) & mask) {
      int prevMask = mask ^ addMask;
      int length = __builtin_popcount(addMask) + 1;
      if (dp[prevMask] == -1 ||
          (dp[mask] != -1 && dp[mask] <= dp[prevMask] + length)) {
        continue;
      }
      bool found = false;
      for (int u = 0; !found && u < n; ++u) {
        if (!(mask & (1 << u))) {
          continue;
        }
        for (int v = 0; !found && v < n; ++v) {
          if (!(mask & (1 << v)) || hasPath[u][v][addMask] == -1) {
            continue;
          }
          dp[mask] = dp[prevMask] + length;
          from[mask] = {u, v, addMask};
          found = true;
        }
      }
    }
  }
  if (dp[(1 << n) - 1] == -1) {
    cout << -1 << endl;
  } else {
    cout << dp[(1 << n) - 1] << endl;
    int mask = (1 << n) - 1;
    while (mask != 1) {
      auto [u, v, addMask] = from[mask];
      mask ^= addMask;
      while (addMask) {
        int prev = hasPath[u][v][addMask];
        cout << v + 1 << " " << prev + 1 << endl;
        addMask ^= (1 << prev);
        v = prev;
      }
      cout << v + 1 << " " << u + 1 << endl;
    }
  }
  return 0;
}
