/*# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")*/
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll mod = 998244353;
const ll INF = 1LL << 60;
const int MAX = 1e9 + 10;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rep2(i, l, r) for (int i = (l); i < (int)(r); i++)
#define repd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repd1(i, n) for (int i = (int)(n); i >= 1; i--)
#define repd2(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); i--)
template<class T> bool chmin(T &a, T b) {
if (a > b) {
a = b; return 1;
}
return 0;
}
template<class T> bool chmax(T &a, T b) {
if (a < b) {
a = b; return 1;
}
return 0;
}
struct edge {
int to, x, y;
};
ll inv(ll a) {
ll b = mod, u = 1, v = 0;
while(b) {
ll t = a / b;
a -= b * t;
swap(a, b);
u -= v * t;
swap(u, v);
}
u %= mod;
if (u < 0) u += mod;
return u;
}
template<class T> void print(vector<T> a) {
int n = a.size();
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
}
template<class T> int low_idx(const vector<T> &a, T x) {
return distance(a.begin(), lower_bound(a.begin(), a.end(), x));
}
template<class T> bool next_combination(T &bit, int N) {
T x = bit & -bit, y = bit + x;
bit = (((bit & ~y) / x) >> 1) | y;
return (bit < (1LL << N));
}
int next_combination(int sub) {
int x = sub & -sub, y = sub + x;
return (((sub & ~y) / x) >> 1) | y;
}
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m; cin >> n >> m;
vector<int> b(m), t(m);
rep(i, m) cin >> b[i] >> t[i];
vector<int> idx(m * 2, 0);
rep(i, n) {
idx[i * 2] = i + 1;
idx[i * 2 + 1] = i + 1;
}
sort(idx.begin(), idx.end());
vector<vector<edge>> G(2520), Grev(2520);
map<vector<int>, int> mp;
set<int> last;
vector<vector<int>> lis; lis.reserve(2520);
do {
rep(i, m) {
if (idx[i * 2] == 0 && idx[i * 2 + 1] > 0) continue;
}
mp[idx] = lis.size(); lis.push_back(idx);
bool fin = 1;
rep(i, m) fin &= (idx[i * 2] == idx[i * 2 + 1]);
if (fin) last.insert(lis.size()-1);
} while (next_permutation(idx.begin(), idx.end()));
int cur = 0;
sort(idx.begin(), idx.end());
do {
rep(i, m) {
if (idx[i * 2] == 0 && idx[i * 2 + 1] > 0) continue;
}
vector<int> copy = idx;
bool fin = 1;
rep(i, m) fin &= (idx[i * 2] == idx[i * 2 + 1]);
rep(i, m) rep(j, m) {
if (i == j) continue;
if (idx[i * 2] == 0 && idx[i * 2 + 1] == 0) continue;
if (idx[j * 2 + 1] > 0) continue;
int l = i * 2 + 1, r = j * 2;
if (idx[l] == 0) l--;
if (idx[r] > 0) r++;
if (r % 2 == 1 && idx[r-1] != idx[l]) continue;
swap(copy[l], copy[r]);
G[cur].push_back({mp[copy], i, j});
Grev[mp[copy]].push_back({(int)cur, i, j});
swap(copy[l], copy[r]);
}
cur++;
} while (next_permutation(idx.begin(), idx.end()));
vector<int> init(m * 2);
rep(i, m) {
init[i * 2] = b[i]; init[i * 2 + 1] = t[i];
}
int initial = mp[init];
queue<int> todo;
vector<int> dist(2520, -1); todo.push(initial); dist[todo.front()] = 0;
while (!todo.empty()) {
int now = todo.front();
if (last.count(now)) break;
todo.pop();
for (auto e : G[now]) {
if (dist[e.to] == -1) {
dist[e.to] = dist[now] + 1; todo.push(e.to);
}
}
}
if (todo.empty()) {
cout << -1 << endl; return 0;
}
vector<pair<int, int>> res;
int cur_pos = todo.front();
//print(lis[cur_pos]);
while (cur_pos != initial) {
for (auto e : Grev[cur_pos]) {
if (dist[e.to] == dist[cur_pos] - 1) {
res.push_back({e.x, e.y});
cur_pos = e.to;
//print(lis[cur_pos]);
//cerr << e.x << " " << e.y << endl;
break;
}
}
}
reverse(res.begin(), res.end());
cout << res.size() << endl;
for (auto [x, y] : res) cout << x + 1 << " " << y + 1 << endl;
}
