#include <bits/stdc++.h>
using namespace std;
int fa[15];
int n;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool check(vector<pair<int, int> > &v) {
  random_shuffle(v.begin(), v.end());
  for (int i = 0; i < v.size(); i++) {
    int tot = n;
    for (int i = 1; i <= n; i++) {
      fa[i] = i;
    }
    for (int j = 0; j < v.size(); j++) {
      if (i == j) continue;
      if (find(v[j].first) != find(v[j].second)) {
        fa[find(v[j].first)] = find(v[j].second);
        tot--;
        if (tot == 1) break;
      }
    }
    if (tot != 1) return 0;
  }
  return 1;
}
int main() {
  srand((int)time(NULL));
  int m;
  scanf("%d%d", &n, &m);
  vector<pair<int, int> > v;
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    v.push_back(make_pair(x, y));
  }
  int T = 0;
  vector<pair<int, int> > cur = v;
  vector<pair<int, int> > ans = v;
  while (clock() <= 1900) {
    if (T == 1000) {
      if (ans.size() > cur.size()) ans = cur;
      T = 0, cur = v;
    }
    int x = rand() % cur.size();
    vector<pair<int, int> > tmp = cur;
    tmp.erase(tmp.begin() + x);
    if (check(tmp)) {
      if (rand() % 4 > 0) cur = tmp;
    }
    T++;
  }
  if (ans.size() > cur.size()) ans = cur;
  printf("%d\n", ans.size());
  for (int i = 0; i < ans.size(); i++) {
    printf("%d %d\n", ans[i].first, ans[i].second);
  }
  return 0;
}
