#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  long long n, m;
  cin >> n >> m;
  vector<vector<long long>> adj((size_t)n);
  vector<pair<long long, long long>> all_edges;
  vector<vector<long long>> edges_indexes((size_t)n,
                                          vector<long long>((size_t)n, -1));
  for (long long i = 0; i < m; i++) {
    long long u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].push_back(v);
    adj[v].push_back(u);
    edges_indexes[u][v] = all_edges.size();
    edges_indexes[v][u] = all_edges.size();
    all_edges.emplace_back(min(u, v), max(u, v));
  }
  vector<vector<vector<long long>>> a(
      (size_t)n, vector<vector<long long>>(
                     (size_t)n, vector<long long>((size_t)1 << n, -2)));
  auto restore_path = [&](long long x, long long y, long long add_mask) {
    vector<long long> path;
    y = a[x][y][add_mask], add_mask &= ~(1 << y);
    for (; y >= 0; y = a[x][y][add_mask], add_mask &= ~(1 << y)) {
      path.push_back(y);
    }
    reverse(path.begin(), path.end());
    return path;
  };
  auto edge_shift = [&](long long edge_index) {
    return edge_index < 64
               ? pair<long long, long long>{0, (long long)1 << edge_index}
               : pair<long long, long long>{(long long)1 << (edge_index - 64),
                                            0};
  };
  auto edges_or = [&](pair<long long, long long> x,
                      pair<long long, long long> y) {
    return pair<long long, long long>{x.first | y.first, x.second | y.second};
  };
  auto edges_and = [&](pair<long long, long long> x,
                       pair<long long, long long> y) {
    return pair<long long, long long>{x.first & y.first, x.second & y.second};
  };
  auto size = [&](long long x) {
    return __builtin_popcount(x) + __builtin_popcount(x >> 32);
  };
  auto edges_size = [&](pair<long long, long long> x) {
    return size(x.first) + size(x.second);
  };
  auto restore_edges = [&](long long x, long long y, long long add_mask) {
    pair<long long, long long> edges;
    vector<long long> path = restore_path(x, y, add_mask);
    for (long long i = 0; i <= path.size(); i++) {
      edges = edges_or(
          edges, edge_shift(edges_indexes[i == 0 ? x : path[i - 1]]
                                         [i == path.size() ? y : path[i]]));
    }
    return edges;
  };
  for (long long u = 0; u < n; u++) {
    for (long long v : adj[u]) {
      a[u][v][0] = -1;
    }
  }
  for (long long add_mask = 0; add_mask < 1 << n; add_mask++) {
    for (long long x = 0; x < n; x++) {
      for (long long y = 0; y < n; y++) {
        if ((add_mask & (1 << y)) == 0 && a[x][y][add_mask] != -2) {
          pair<long long, long long> edges = restore_edges(x, y, add_mask);
          for (long long z : adj[y]) {
            if (edges_and(edges, edge_shift(edges_indexes[y][z])) ==
                pair<long long, long long>{0, 0}) {
              a[x][z][add_mask | (1 << y)] = y;
            }
          }
        }
      }
    }
  }
  vector<pair<long long, long long>> b((size_t)1 << n, {-1, -1});
  b[1] = {0, 0};
  for (int mask = 0; mask < 1 << n; mask++) {
    if (b[mask] != pair<long long, long long>{-1, -1}) {
      for (int add_mask = mask ^ ((1 << n) - 1); add_mask > 0;
           add_mask = (add_mask - 1) & (mask ^ ((1 << n) - 1))) {
        if (edges_size(b[mask]) + size(add_mask) <
            edges_size(b[mask | add_mask])) {
          for (long long x = 0; x < n; x++) {
            for (long long y = 0; y < n; y++) {
              if ((mask & (1 << x)) != 0 && (mask & (1 << y)) != 0) {
                if (a[x][y][add_mask] != -2 &&
                    edges_size(b[mask]) +
                            edges_size(restore_edges(x, y, add_mask)) <
                        edges_size(b[mask | add_mask])) {
                  b[mask | add_mask] =
                      edges_or(b[mask], restore_edges(x, y, add_mask));
                }
              }
            }
          }
        }
      }
    }
  }
  cout << edges_size(b[(1 << n) - 1]) << endl;
  for (long long i = 0; i < all_edges.size(); i++) {
    if (edges_and(b[(1 << n) - 1], edge_shift(i)) !=
        pair<long long, long long>{0, 0}) {
      cout << all_edges[i].first + 1 << " " << all_edges[i].second + 1 << endl;
    }
  }
  return 0;
}
