#include <bits/stdc++.h>
template <typename T>
void read(T &x);
template <typename T>
void read(T &x, T &y);
template <typename T>
void read(T &x, T &y, T &z);
template <typename T>
void write(T x);
template <typename T>
void writeC(T x);
template <typename T>
void writeN(T x);
long long f[15][1 << 14][15], dp[1 << 14], u, v, G[20][20], n, m,
    cycle[1 << 14];
long long w(long long x) { return (1 << (x - 1)); }
void build_path(long long u, long long v, long long mask) {
  if (u == v) return;
  for (long long x = 1; x <= n; ++x) {
    if (x == v || (!(mask & w(x)))) continue;
    if (G[x][v] && f[u][mask - (1 << (v - 1))][x]) {
      printf("%d %d\n", x, v);
      build_path(u, x, mask - (1 << (v - 1)));
      return;
    }
  }
}
void build_cycle(long long mask) {
  long long u = 0, v = 0;
  for (long long i = 1; i <= n; ++i)
    for (long long j = i + 1; j <= n; ++j)
      if ((mask & w(i)) && (mask & w(j)) && G[i][j] && f[i][mask][j]) {
        u = i;
        v = j;
      }
  printf("%d %d\n", u, v);
  build_path(u, v, mask);
}
void output(long long mask) {
  if (!mask) return;
  if (cycle[mask] && dp[mask] == __builtin_popcount(mask)) {
    build_cycle(mask);
    return;
  }
  for (long long sub = mask; sub; sub = (sub - 1) & mask) {
    if (cycle[sub]) {
      for (long long j = 1; j <= n; ++j) {
        if (!(sub & w(j))) continue;
        long long wx = dp[mask - sub + w(j)] + __builtin_popcount(sub);
        if (wx == dp[mask]) {
          build_cycle(sub);
          output(mask - sub + w(j));
          return;
        }
      }
    }
    for (long long u = 1; u <= n; ++u) {
      for (long long v = u + 1; v <= n; ++v) {
        if ((!(sub & w(u))) || (!(sub & w(v)))) continue;
        if (f[u][sub][v]) {
          long long wx =
              dp[mask - sub + w(u) + w(v)] + __builtin_popcount(sub) - 1;
          if (wx == dp[mask]) {
            build_path(u, v, sub);
            output(mask - sub + w(u) + w(v));
            return;
          }
        }
      }
    }
  }
}
signed main() {
  read(n, m);
  for (long long i = (1); i <= (m); ++i) {
    read(u, v);
    G[u][v] = G[v][u] = 1;
  }
  for (long long u = (1); u <= (n); ++u) {
    f[u][1 << (u - 1)][u] = 1;
    for (long long mask = 0; mask < (1 << n); ++mask)
      for (long long i = 1; i <= n; ++i) {
        if (!(mask & (1 << (i - 1)))) continue;
        for (long long j = 1; j <= n; ++j) {
          if ((!(mask & (1 << (j - 1)))) || i == j) continue;
          if (G[i][j]) f[u][mask][i] |= f[u][mask - w(i)][j];
        }
      }
    for (long long v = (1); v <= (n); ++v) {
      for (long long mask = 0; mask < (1 << n); ++mask) {
        if (f[u][mask][v] && G[u][v] && __builtin_popcount(mask) > 2)
          cycle[mask] = 1;
      }
    }
  }
  std::memset(dp, 63, sizeof(dp));
  dp[0] = 0;
  for (long long mask = 1; mask < (1 << n); ++mask) {
    if (cycle[mask]) dp[mask] = __builtin_popcount(mask);
    for (long long sub = mask; sub; sub = (sub - 1) & mask) {
      if (cycle[sub]) {
        for (long long j = 1; j <= n; ++j) {
          if (!(sub & w(j))) continue;
          dp[mask] = std::min(dp[mask], dp[mask - sub + (1 << (j - 1))] +
                                            __builtin_popcount(sub));
        }
      }
      for (long long u = 1; u <= n; ++u) {
        for (long long v = u + 1; v <= n; ++v) {
          if ((!(sub & w(u))) || (!(sub & w(v)))) continue;
          if (f[u][sub][v]) {
            long long wx =
                dp[mask - sub + w(u) + w(v)] + __builtin_popcount(sub) - 1;
            dp[mask] = std::min(dp[mask], wx);
          }
        }
      }
    }
  }
  printf("%d\n", dp[(1 << n) - 1]);
  output((1 << n) - 1);
}
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T flag = 1;
  while (c < '0' || c > '9') {
    if (c == '-') flag = -flag;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= flag;
}
template <typename T>
void read(T &x, T &y) {
  read(x);
  read(y);
}
template <typename T>
void read(T &x, T &y, T &z) {
  read(x);
  read(y);
  read(z);
}
template <typename T>
void writeC(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) writeC(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void write(T x) {
  writeC(x);
  putchar(' ');
}
template <typename T>
void writeN(T x) {
  writeC(x);
  puts("");
}
