#include <bits/stdc++.h>
using namespace std;
int n, m, d[20], rb[20], back[20];
pair<int, int> bb[20];
vector<int> v[20];
vector<pair<int, int>> ans, cur;
mt19937 rng;
int ta, tb;
void dfs(int a, int b) {
  shuffle(v[a].begin(), v[a].end(), rng);
  rb[a] = back[a] = d[a];
  for (int i : v[a])
    if (i != b)
      if (!d[i]) {
        cur.emplace_back(a, i);
        d[i] = d[a] + 1;
        dfs(i, a);
        rb[a] = min(rb[a], rb[i]);
        if (back[i] < back[a]) {
          back[a] = back[i];
          bb[a] = bb[i];
        }
      } else if (d[i] < back[a]) {
        back[a] = d[i];
        bb[a] = {a, i};
      }
  if (b && rb[a] == d[a]) {
    cur.push_back(bb[a]);
    rb[a] = back[a];
  }
}
int main() {
  auto st = chrono::high_resolution_clock::now();
  rng = mt19937(st.time_since_epoch().count());
  scanf("%d%d", &n, &m);
  n = n + 10000000;
  m -= 10000000;
  n -= 10000000;
  m = m + 10000000;
  int now = 0;
  while (now < 20000000) now++;
  while (m--) {
    scanf("%d%d", &ta, &tb);
    int x = ta + tb, y = ta - tb;
    v[ta].push_back(tb);
    v[tb].push_back(ta);
    int z = x + y;
  }
  for (int i = 0; i < 1000; i++) {
    cur.clear();
    memset(d + 1, 0, sizeof(d[0]) * n);
    int tmp = uniform_int_distribution<int>(1, n)(rng);
    d[tmp] = 1;
    dfs(tmp, 0);
    if (ans.empty() || cur.size() < ans.size()) ans = cur;
  }
  printf("%d\n", (int)ans.size());
  for (auto& i : ans) printf("%d %d\n", i.first, i.second);
}
