#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
  return x * f;
}
int n, m;
vector<int> G[20], G2[20];
int low[20], dfn[20];
int cur;
bool tarjan(int u, int fa) {
  bool flg = 0;
  low[u] = dfn[u] = ++cur;
  bool flg2 = 1;
  for (auto v : G2[u]) {
    if (!dfn[v]) {
      if (!tarjan(v, u)) flg2 = 0;
      low[u] = min(low[u], low[v]);
      if (dfn[v] == low[v]) flg2 = 0;
    } else if (v != fa || flg)
      low[u] = min(low[u], dfn[v]);
    else
      flg = 1;
  }
  return flg2;
}
vector<pair<int, int> > del;
int curcnt;
int ans = 0x3f3f3f3f;
vector<int> Gans[20];
void delete_edge(int x) {
  if (!x) return;
  if (G2[x].empty()) return;
  int rrrnd = (rand() % G2[x].size() + G2[x].size()) % G2[x].size();
  int y = G2[x][rrrnd];
  del.emplace_back(x, y);
  G2[x].erase(find(G2[x].begin(), G2[x].end(), y));
  G2[y].erase(find(G2[y].begin(), G2[y].end(), x));
  memset(low, 0, sizeof low);
  memset(dfn, 0, sizeof dfn);
  cur = 0;
  if (!tarjan(1, -1)) {
  Ret:
    G2[x].push_back(y);
    G2[y].push_back(x);
    del.pop_back();
    return;
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) goto Ret;
  curcnt--;
  if (curcnt < ans) {
    ans = curcnt;
    for (int i = 1; i <= n; i++) Gans[i] = G2[i];
  }
}
void add_edge(int x) {
  if (del.empty()) return;
  G2[del[x].first].push_back(del[x].second);
  G2[del[x].second].push_back(del[x].first);
  del.erase(del.begin() + x);
  curcnt++;
}
int main() {
  srand(19260817);
  int stt = clock();
  n = read(), m = read();
  for (int i = 1, x, y; i <= m; i++) {
    x = read(), y = read();
    G[x].push_back(y);
    G[y].push_back(x);
  }
  curcnt = ans = m;
  for (int i = 1; i <= n; i++) Gans[i] = G[i];
  const int max_time = 1950;
  for (int _ = 1; _ <= 1000; _++) {
    for (int i = 1; i <= n; i++) G2[i] = G[i];
    curcnt = m;
    for (int __ = 1; __ <= 1000; __++) {
      if (rand() % 4)
        delete_edge((rand() % n + n) % n + 1);
      else if (!del.empty()) {
        add_edge(rand() % del.size());
      }
    }
    if (clock() - stt > max_time) break;
  }
  printf("%d\n", ans);
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < Gans[i].size(); j++)
      if (Gans[i][j] > i) printf("%d %d\n", i, Gans[i][j]);
  return 0;
}
