#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 5e5+5;
int place[nax][2];
int park[nax][2];
int outdeg[nax];
vector<int> dag[nax];
vector<int> adj[nax];
set<int> fre;
bool vis[nax];
int cycle[nax];
vector<int> cur,concur;
bool test=false;
vector<pair<int,int>> ans;
vector<int> topo;
void deplace(int x,int y){
ans.push_back({x,y});
int topx = 1 - (park[x][0] == 0) - (park[x][1] == 0);
int topy = 1 - (park[y][0] == 0) - (park[y][1] == 0);
int vx = park[x][topx];
park[y][topy+1] = vx;
int indx=0;
if(place[vx][1] == x) indx=1;
place[vx][indx]=y;
park[x][topx] = 0;
if(topx == 0) fre.insert(x);
if(topy==-1){
if (indx == 1) swap(place[vx][0] , place[vx][1]);
fre.erase(y);
}
}
void dfs(int x){
if(cycle[x]==1){
test=true;
return;
}
if(test) return;
cycle[x]=1;
for(auto u : dag[x]){
dfs(u);
}
cycle[x]=2;
cur.push_back(x);
}
void dfs1(int x){
vis[x]=true;
concur.push_back(x);
for(auto u : adj[x]){
if(!vis[u]) dfs1(u);
}
}
void run_case(){
int n,m;
cin>>n>>m;
for (int i = 1; i <= n; ++i) place[i][0]=place[i][1]=-1;
for (int i = 1; i <= m; ++i)
{
cin>>park[i][0]>>park[i][1];
if(park[i][0]+park[i][1]==0) fre.insert(i);
if(park[i][0]==park[i][1]) continue;
if(place[park[i][0]][0] == -1) place[park[i][0]][0] = i;
else place[park[i][0]][1] = i;
if(park[i][1] != 0){
if(place[park[i][1]][1] == -1) place[park[i][1]][1] = i;
else place[park[i][1]][0] = i;
//cout <<park[i][1]<<" "<< place[park[i][1]][0] <<" "<< place[park[i][1]][0]<< endl;
}
dag[park[i][1]].push_back(park[i][0]);
outdeg[park[i][1]]++;
adj[park[i][1]].push_back(park[i][0]);
adj[park[i][0]].push_back(park[i][1]);
}
//cout << place[1][0] << " "<<place[1][1]<<endl;
for (int i = 1; i <= n; ++i)
{
if(place[i][0]==place[i][1]) continue;
if(!vis[i]){
test=false;
cur.clear();
concur.clear();
dfs1(i);
for(auto u : concur) dfs(i);
if(test){
if(fre.empty()){
cout << -1 << endl;
return;
}else{
int cnt = *fre.begin();
int lst=cnt;
for(auto u : cur){
int temp = place[u][1];
deplace(place[u][1] , lst);
lst = temp;
}
deplace(lst , cnt);
}
}else{
for(auto u : cur) topo.push_back(u);
}
}
}
reverse(topo.begin(),topo.end());
for(auto u : topo){
if(place[u][0]==place[u][1]) continue;
if(outdeg[u] == 2){
if(fre.empty()){
cout << -1 <<endl;
return;
}
int pivot = *fre.begin();
int y = place[u][1];
deplace(place[u][0] , pivot);
deplace(y , pivot);
}else if(outdeg[u] == 1){
deplace(place[u][1] , place[u][0]);
}else if(outdeg[u] == 0){
deplace(place[u][1] , place[u][0]);
}
}
cout << ans.size() << endl;
for (auto u : ans)
{
cout << u.fi << " " << u.se << endl;
}
}
int main() {
run_case();
}
# | 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... |