#include<bits/stdc++.h>
using namespace std;
using ll = long long;
signed main()
{
int n , m;
cin>>n>>m;
vector<int> t(m) , b(m);
vector<int> f(2 * n + 1 , -1);
vector<pair<int ,int>> ops;
stack<int> empty;
for(int i = 0 ; i < m ; i++)
{
cin>>b[i]>>t[i];
if(b[i] == 0)
{
empty.push(i);
continue;
}
}
vector<int> nb(n + 1);
for(int j = 0 ; j < n ; j++)
{
for(int i = 0 ; i < m ; i++)
{
if(b[i] == 0)
continue;
if(b[i] == t[i])
continue;
if(t[i] && nb[t[i]] < 2)
{
if(f[t[i]] == -1 || f[t[i]] == i)
{
if(f[t[i]] == i)
continue;
int l = 0;
for( ; l < m ; l++)
{
if(b[l] == 0)
{
break;
}
}
if(l >= m)
continue;
empty.pop();
ops.push_back({l , i});
nb[t[i]]++;
f[t[i]] = l;
swap(t[i] , b[l]);
}
else
{
nb[t[i]]++;
ops.push_back({f[t[i]] , i});
swap(t[i] , t[f[t[i]]]);
}
}
if(nb[b[i]] < 2)
{
if(f[b[i]] == -1 || f[b[i]] == i)
{
if(f[b[i]] == -1)
nb[b[i]]++;
f[b[i]] = i;
}
else
{
nb[b[i]]++;
ops.push_back({f[b[i]] , i});
swap(b[i] , t[f[b[i]]]);
}
}
}
}
for(int i = 1 ; i <= n ; i++)
{
if(nb[i] != 2)
{
cout<<"-1\n";
return 0;
}
}
cout<<(int)ops.size()<<'\n';
for(auto [u , v] : ops)
{
cout<<u + 1<<" "<<v + 1<<'\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |