#include <bits/stdc++.h>
using namespace std;
vector<int> G[14];
int dp[1 << 14], dp2[14][14][1 << 14];
vector<int> re[1 << 14];
pair<int, int> last_pair[1 << 14];
int pre[1 << 14];
int last[14][14][1 << 14];
bool v[1 << 14];
int main() {
  int n, m, x, y;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    G[x - 1].push_back(y - 1);
    G[y - 1].push_back(x - 1);
  }
  for (int i = 0; i < n; i++) v[1 << i] = 1;
  memset(dp, 0x3f, sizeof(dp));
  dp[1] = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < (1 << n); k++) {
        dp2[i][j][k] = 0x3f3f3f3f;
      }
  for (int i = 0; i < n; i++)
    for (auto x : G[i]) {
      dp2[i][x][0] = 1;
      last[i][x][0] = i;
    }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) continue;
      for (int k = 0; k < n; k++) {
        if ((i >> k) & 1) continue;
        if (j == k || dp2[j][k][i] == 0x3f3f3f3f) continue;
        for (auto z : G[k]) {
          if ((i >> z) & 1) continue;
          if (z == last[j][k][i]) continue;
          int tmp = i ^ (1 << k);
          if (dp2[j][z][tmp] == 0x3f3f3f3f) {
            dp2[j][z][tmp] = 1;
            last[j][z][tmp] = k;
          }
        }
      }
    }
  }
  for (int i = 0; i < n; i++) dp[1 << i] = 0;
  for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) re[i].push_back(j);
    }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = i; j; j = (j - 1) & i) {
      int tmp = i ^ j;
      int cnt = __builtin_popcount(j) + 1;
      if (dp[i] < dp[tmp] + cnt) continue;
      for (auto x : re[tmp])
        for (auto y : re[tmp]) {
          if (dp2[x][y][j] == 1) {
            dp[i] = min(dp[i], dp[tmp] + cnt);
            last_pair[i] = make_pair(x, y);
            pre[i] = tmp;
          }
        }
    }
  }
  if (dp[(1 << n) - 1] == 0x3f3f3f3f) {
    printf("-1\n");
  } else {
    printf("%d\n", dp[(1 << n) - 1]);
    int now = (1 << n) - 1;
    while (!v[now]) {
      int x = last_pair[now].first, y = last_pair[now].second;
      int tmp = now ^ pre[now];
      while (tmp) {
        int tmp1 = last[x][y][tmp];
        printf("%d %d\n", y + 1, tmp1 + 1);
        y = tmp1;
        tmp ^= (1 << tmp1);
      }
      printf("%d %d\n", x + 1, y + 1);
      now = pre[now];
    }
  }
}
