#include<bits/stdc++.h>
using namespace std;
int n,m;
int sus[200005],jos[200005];
///0 - jos
///1 - sus
///2 - singur
pair<pair<int,int>,pair<int,int>> pozs[200005];///{poz,tip}
set<int> libere;
set<int> s[3][3];
void sort_car(int i)
{
if(pozs[i].first.second > pozs[i].second.second)
swap(pozs[i].first, pozs[i].second);
}
void scoate(int i)
{
if(i==0)
return;
assert(pozs[i].first.first != 0);
assert(pozs[i].second.first != 0);
sort_car(i);
s[pozs[i].first.second][pozs[i].second.second].erase(i);
}
void baga(int i)
{
if(i==0)
return;
assert(pozs[i].first.first != 0);
assert(pozs[i].second.first != 0);
sort_car(i);
if(pozs[i].first.first != pozs[i].second.first)
s[pozs[i].first.second][pozs[i].second.second].insert(i);
}
int remove_car(int poz)
{
assert(jos[poz]);
if(sus[poz])
{
int car = sus[poz];
sus[poz] = 0;
if(pozs[car].first.first == poz)
swap(pozs[car].first, pozs[car].second);
pozs[car].second = {0, -1};
if(pozs[jos[poz]].second.first == poz)
swap(pozs[jos[poz]].first, pozs[jos[poz]].second);
pozs[jos[poz]].first = {poz, 2};
return car;
}
else
{
int car = jos[poz];
jos[poz] = 0;
libere.insert(poz);
if(pozs[car].first.first == poz)
swap(pozs[car].first, pozs[car].second);
pozs[car].second = {0, -1};
return car;
}
}
void add_car(int poz, int car)
{
assert(sus[poz]==0);
if(jos[poz]==0)
{
libere.erase(poz);
jos[poz] = car;
pozs[car].second = {poz, 2};
}
else
{
sus[poz] = car;
pozs[car].second = {poz, 1};
if(pozs[jos[poz]].second.first == poz)
swap(pozs[jos[poz]].first, pozs[jos[poz]].second);
pozs[jos[poz]].first = {poz, 0};
}
}
vector<pair<int,int>> sol;
void move_car(int from, int to)
{
scoate(jos[from]);
scoate(sus[from]);
scoate(jos[to]);
scoate(sus[to]);
int car = remove_car(from);
add_car(to, car);
sol.push_back({from, to});
baga(jos[from]);
baga(sus[from]);
baga(jos[to]);
baga(sus[to]);
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>jos[i]>>sus[i];
if(jos[i]==0)
{
libere.insert(i);
}
else if(sus[i]==0)
{
if(pozs[jos[i]].first.first == 0)
pozs[jos[i]].first = {i, 2};
else
pozs[jos[i]].second = {i, 2};
}
else
{
if(pozs[jos[i]].first.first == 0)
pozs[jos[i]].first = {i, 0};
else
pozs[jos[i]].second = {i, 0};
if(pozs[sus[i]].first.first == 0)
pozs[sus[i]].first = {i, 1};
else
pozs[sus[i]].second = {i, 1};
}
}
for(int i=1;i<=n;i++)
baga(i);
while(1)
{
if(!s[2][2].empty())
{
int car = *s[2][2].begin();
move_car(pozs[car].first.first, pozs[car].second.first);
}
else if(!s[1][2].empty())
{
int car = *s[1][2].begin();
move_car(pozs[car].first.first, pozs[car].second.first);
}
else if(!s[1][1].empty())
{
if(libere.empty())
{
cout<<-1;
return 0;
}
int car = *s[1][1].begin();
int poz = *libere.begin();
int p0 = pozs[car].first.first, p1 = pozs[car].second.first;
move_car(p0, poz);
move_car(p1, poz);
}
else if(!s[0][2].empty())
{
if(libere.empty())
{
cout<<-1;
return 0;
}
int car = *s[0][2].begin();
int poz = *libere.begin();
sort_car(car);
int p0 = pozs[car].first.first, p2 = pozs[car].second.first;
move_car(p0, poz);
move_car(p2, p0);
}
else if(!s[0][1].empty())
{
if(libere.empty())
{
cout<<-1;
return 0;
}
int car = *s[0][1].begin();
int poz = *libere.begin();
sort_car(car);
int p0 = pozs[car].first.first, p1 = pozs[car].second.first;
move_car(p0, poz);
move_car(p1, p0);
}
else
{
break;
}
}
cout<<(int)sol.size()<<"\n";
for(auto [x,y]:sol)
cout<<x<<" "<<y<<"\n";
return 0;
}
