#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void apply_op(int i , int j , vector<int> &t , vector<int> &b , vector<pair<int ,int>> &ops)
{
int whati = 1; // top
if(t[i] == 0)
whati = 0;
int whatj = 1;
if(b[j] == 0)
whatj = 0;
swap((whati ? t[i] : b[i]) , (whatj ? t[j] : b[j]));
}
signed main()
{
int n , m;
cin>>n>>m;
vector<int> t(m) , b(m);
vector<pair<int ,int>> ops;
for(int i = 0 ; i < m ; i++)
{
cin>>b[i]>>t[i];
}
while(true)
{
bool barra = 0;
for(int i = 0 ; i < m ; i++)
{
if(t[i] != b[i])
{
barra = 1;
break;
}
}
if(!barra)
break;
vector<vector<pair<int , int>>> v(n + 1);
int emp = -1;
for(int i = 0 ; i < m ; i++)
{
if(b[i] == 0)
emp = i;
else
{
if(b[i] == t[i])
continue;
if(t[i])
v[t[i]].push_back({1 , i});
v[b[i]].push_back({0 , i});
}
}
bool check = 0;
for(int i = 1 ; i <= n ; i++)
{
if(v[i].size() == 2)
{
sort(v[i].begin() , v[i].end());
if(v[i][0].first == 0)
{
int idx1 = v[i][0].second;
int idx2 = v[i][1].second;
if(t[idx1] == 0)
{
if(v[i][1].first == 1 || t[idx2] == 0)
{
ops.push_back({idx2 , idx1});
apply_op(idx2 , idx1 , t , b , ops);
check = 1;
break;
}
}
}
}
}
if(check)
continue;
check = 0;
if(emp != -1)
{
for(int i = 0 ; i < m ; i++)
{
if(t[i] )
{
ops.push_back({i , emp});
apply_op(i , emp , t , b , ops);
check = 1;
break;
}
}
}
if(!check)
{
cout<<"-1\n";
return 0;
}
}
for(int i = 0 ; i < m ; i++)
{
if(b[i] != t[i])
{
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... |