#include <bits/stdc++.h>
using namespace std;
int encryptstate(vector<pair<int, int>> v) {
int ret = 0;
for(pair<int, int> p : v) {
int a, b;
tie(a, b) = p;
ret <<= 8;
ret |= (a << 4) | b;
}
return ret;
}
vector<pair<int, int>> decryptstate(int state, int length) {
vector<pair<int, int>> ret;
for(int i = 8 * length - 8; i >= 0; i -= 8) {
int current = state >> i;
ret.push_back(make_pair((current & 0xf0) >> 4, current & 0xf));
}
return ret;
}
void print(int state, unordered_map<int, tuple<int, int, int>>& states) {
if(get<0>(states[state]) == -1) return;
print(get<0>(states[state]), states);
cout << get<1>(states[state]) + 1 << " " << get<2>(states[state]) + 1 << "\n";
}
int main() {
int N, M;
cin >> N >> M;
unordered_map<int, tuple<int, int, int>> states;
vector<pair<int, int>> start(M);
for(int i = 0; i < M; i++) {
int bot, top;
cin >> bot >> top;
start[i] = make_pair(bot, top);
}
int est = encryptstate(start);
/* for(pair<int, int> p : start) cout << p.first << " " << p.second << ",";
cout << "\n";
for(pair<int, int> p : decryptstate(est, M)) cout << p.first << " " << p.second << ",";
cout << "\n";*/
states[est] = make_tuple(-1, -1, -1);
if((est & 0x0f0f0f0f) == (est & 0xf0f0f0f0) >> 4) {
cout << "0\n";
return 0;
}
bool b = true;
int loop = 0;
while(b) {
loop++;
b = false;
unordered_map<int, tuple<int, int, int>> newstates = states;
for(auto it : states) {
vector<pair<int, int>> stvec = decryptstate(it.first, M);
for(int i = 0; i < M; i++) {
for(int j = 0; j < M; j++) {
if(i == j) continue;
vector<pair<int, int>> newstvec = stvec;
if(newstvec[i].first == 0)
continue;
if(newstvec[j].second != 0)
continue;
int num;
if(stvec[i].second != 0) {
num = stvec[i].second;
newstvec[i].second = 0;
}
else {
num = stvec[i].first;
newstvec[i].first = 0;
}
if(stvec[j].first == 0)
newstvec[j].first = num;
else if(stvec[j].first == num)
newstvec[j].second = num;
else continue;
int enc = encryptstate(newstvec);
if(newstates.find(enc) == newstates.end()) {
//cout << i << " " << j << "\n";
//for(pair<int, int> p : decryptstate(enc, M)) cout << p.first << " " << p.second << ",";
//cout << "\n";
b = true;
newstates[enc] = make_tuple(it.first, i, j);
//cout << "\t" << (enc & 0x33333333) << " " << ((enc & 0xcccccccc) >> 2) << "\n";
if((enc & 0x0f0f0f0f) == (enc & 0xf0f0f0f0) >> 4) {
states[enc] = make_tuple(it.first, i, j);
cout << loop << "\n";
print(enc, states);
return 0;
}
}
}
}
}
states = newstates;
//cout << states.size() << "\n";
}
cout << "-1\n";
return 0;
}
