#include <bits/stdc++.h>
using namespace std;
int g[14][15], n, m, S;
bool lnk[14][14][1 << 14];
int las[14][14][1 << 14];
int bits[1 << 18], dp[1 << 14], LAS[1 << 14];
pair<int, int> LASP[1 << 14];
void add(int x, int y) {
  g[x][++*g[x]] = y;
  lnk[x][y][0] = true;
  las[x][y][0] = x;
}
void Add(int x, int y) {
  add(x, y);
  add(y, x);
}
int main() {
  int i, j, k, x, y, *r, *s, *t, w;
  scanf("%d%d", &n, &m);
  S = (1 << n) - 1;
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    --x;
    --y;
    Add(x, y);
  }
  for (i = 0; i < n; i++) {
    k = g[i][0];
    g[i][0] = g[i][k];
    g[i][k] = -1;
  }
  for (i = 0; i <= S; i++) {
    t = (bits + ((i) << 4));
    for (j = 0; j < n; j++)
      if (i >> j & 1) *t++ = j;
    *t++ = -1;
  }
  for (i = 0; i <= S; i++) {
    for (s = (bits + ((i ^ S) << 4)); ~*s; s++) {
      for (t = (bits + ((i ^ S) << 4)); ~*t; t++) {
        if (s != t && lnk[*s][*t][i]) {
          for (r = g[*t]; ~*r; r++) {
            if (*r != las[*s][*t][i] && !lnk[*s][*r][i | (1 << *t)]) {
              lnk[*s][*r][i | (1 << *t)] = 1;
              las[*s][*r][i | (1 << *t)] = *t;
            }
          }
        }
      }
    }
  }
  memset(dp, 0x60, sizeof dp);
  dp[1] = 0;
  for (i = 0; i <= S; i++) {
    for (j = i; j; j = j - 1 & i) {
      w = __builtin_popcount(j) + 1;
      k = j ^ i;
      if (w + dp[k] >= dp[i]) continue;
      bool flag = false;
      for (s = (bits + ((k) << 4)); ~*s; s++) {
        for (t = (bits + ((k) << 4)); ~*t; t++) {
          if (lnk[*s][*t][j]) {
            flag = true;
            LAS[i] = j;
            dp[i] = w + dp[k];
            LASP[i] = make_pair(*s, *t);
          }
          if (flag) break;
        }
        if (flag) break;
      }
    }
  }
  if (dp[S] == 0x60606060) {
    puts("-1");
  } else {
    printf("%d\n", dp[S]);
    while (S != 1) {
      k = LAS[S];
      x = LASP[S].first;
      y = LASP[S].second;
      S ^= k;
      while (1) {
        printf("%d %d\n", las[x][y][k] + 1, y + 1);
        if (!k) break;
        y = las[x][y][k];
        k ^= 1 << y;
      }
    }
  }
}
