#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
pair<int, int> Parking[N];
pair<int, int> Positions[N];
//0 - bottom, 1 - top
pair<int, bool> Graph[N][2];
bitset<N> visited;
vector<int> Free;
vector<pair<int, int>> Solution;
void AddMove(int a, int b)
{
Solution.push_back({a, b});
if(Parking[b].first == 0) {
if(Parking[a].second != 0)
swap(Parking[a].second, Parking[b].first);
else
swap(Parking[a].first, Parking[b].first);
} else {
if(Parking[a].second != 0)
swap(Parking[a].second, Parking[b].second);
else
swap(Parking[a].first, Parking[b].second);
}
}
// void Fix(int n)
// {
// for(int i = 1; i <= n; i++) {
// auto [pos1, pos2] = Positions[i];
// if(Parking[pos2].second == 0)
// swap(pos1, pos2);
// if(Parking[pos1].second == 0) {
// if(Parking[pos2].second == 0) {
// Solution.push_back({pos2, pos1});
// Free.push_back(pos2);
// Parking[pos2] = {0, 0};
// Parking[pos1] = {i, i};
// } else if(Parking[pos2].second == i) {
// Solution.push_back({pos2, pos1});
// Parking[pos2].second = 0;
// Parking[pos1] = {i, i};
// }
// }
// }
// }
bool BuildGraph(int n)
{
bool work = true;
for(int i = 1; i <= n; i++) {
if(Positions[i].first == Positions[i].second)
continue;
work = false;
bool a1 = (Parking[Positions[i].first].second == i);
bool a2 = (Parking[Positions[i].second].second == i);
Graph[Positions[i].first][a1] = {Positions[i].second, a2};
Graph[Positions[i].second][a2] = {Positions[i].first, a1};
}
return work;
}
pair<int, int> needed = {-1, -1};
int Fun(int u)
{
int vertex = u;
vector<pair<int, int>> Add;
while(Graph[vertex][1].second != 1 && Graph[vertex][1].first != -1) {
Add.push_back({vertex, Graph[vertex][1].first});
vertex = Graph[vertex][1].first;
visited[vertex];
}
if(Graph[vertex][1].first == -1) {
while(!Add.empty()) {
AddMove(Add.back().first, Add.back().second);
Add.pop_back();
}
return -1;
}
if(Free.size() == 0)
return 0;
AddMove(vertex, Free.back());
AddMove(Graph[vertex][1].first, Free.back());
Free.pop_back();
while(!Add.empty()) {
AddMove(Add.back().first, Add.back().second);
Add.pop_back();
}
return Graph[vertex][1].first;
}
bool DFS1(int u, bool which)
{
visited[u] = 1;
if(which == 0) {
if(Graph[u][0].second == 1) {
AddMove(Graph[u][0].first, u);
if(!DFS1(Graph[u][0].first, 0))
return false;
} else {
needed = {u, Graph[u][0].first};
if(!DFS1(Graph[u][0].first, 1))
return false;
}
} else {
if(Graph[u][1].second == 0) {
int x = Fun(u);
if(x == 0)
return false;
if(needed.first != -1) {
AddMove(needed.first, needed.second);
Free.push_back(needed.first);
needed = {-1, -1};
}
if(x != -1) {
if(!DFS1(x, 0))
return false;
}
} else if(Graph[u][1].first != -1) {
if(Free.size() == 0)
return false;
AddMove(u, Free.back());
AddMove(Graph[u][1].first, Free.back());
Free.pop_back();
if(needed.first != -1) {
AddMove(needed.first, needed.second);
Free.push_back(needed.first);
needed = {-1, -1};
}
if(!DFS1(Graph[u][1].first, 0))
return false;
} else {
if(needed.first != -1) {
AddMove(needed.first, needed.second);
Free.push_back(needed.first);
needed = {-1, -1};
}
}
}
return true;
}
void DFS2(int u, int pos)
{
visited[u] = 1;
AddMove(u, pos);
if(!visited[Graph[u][0].first])
DFS2(Graph[u][0].first, u);
}
bool Solve(int n, int m)
{
for(int i = 1; i <= m; i++) {
if(!visited[i] && Parking[i].first != Parking[i].second) {
if(Graph[i][1].second == 1) {
if(Free.size() == 0)
return false;
AddMove(i, Free.back());
AddMove(Graph[i][1].first, Free.back());
Free.pop_back();
Graph[Graph[i][1].first][1].first = -1;
Graph[i][1].first = -1;
if(!DFS1(i, 0))
return false;
}
}
}
for(int i = 1; i <= m; i++) {
if(!visited[i] && Parking[i].first != Parking[i].second) {
if(Free.size() == 0)
return false;
int c = Parking[i].second;
DFS2(i, Free.back());
if(Positions[c].first == i)
swap(Positions[c].first, Positions[c].second);
AddMove(Free.back(), Positions[c].first);
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, a, b;
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> a >> b;
Parking[i] = {a, b};
if(a == 0 && b == 0)
Free.push_back(i);
if(Positions[a].first == 0)
Positions[a].first = i;
else
Positions[a].second = i;
if(Positions[b].first == 0)
Positions[b].first = i;
else
Positions[b].second = i;
}
// Fix(n);
if(BuildGraph(n)) {
cout << Solution.size() << "\n";
for(auto [x, y] : Solution)
cout << x << " " << y << "\n";
}
if(!Solve(n, m))
cout << "-1\n";
else {
cout << Solution.size() << "\n";
for(auto [x, y] : Solution)
cout << x << " " << y << "\n";
}
}
