#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FFOR(i,a,b,c) for(int i=(a);(c)>0?i<=(b):i>=(b);i+=(c))
#define FOOR(i,a,b) FFOR(i,a,(b)-1,1)
#define ROOF(i,a,b) FFOR(i,(b)-1,a,-1)
#define FOR(i,n) FOOR(i,0,n)
#define ROF(i,n) ROOF(i,0,n)
#define FORR(x,v) for(auto &x:v)
#define vc vector
#define sz(v) (int)((v).size())
#define bg begin()
#define en end()
#define em empty()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define ppb pop_back()
#define eb emplace_back
#define bk back()
#define fr front()
#define pp pop()
#define all(v) (v).begin(),(v).end()
#define lla(v) (v).rbegin(),(v).rend()
#define f first
#define s second
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M;
cin>>N>>M;
vc<int> bot(M),top(M),x(N,-1),y(N),free;
FOR(i,M){
cin>>bot[i]>>top[i];
bot[i]--,top[i]--;
if(bot[i]!=-1) (x[bot[i]]==-1?x[bot[i]]:y[bot[i]])=i*2;
if(top[i]!=-1) (x[top[i]]==-1?x[top[i]]:y[top[i]])=i*2+1;
if(bot[i]==-1&&top[i]==-1) free.pb(i);
}
vc<pair<int,int>> ans;
auto move=[&](int u,int v) {
cout<<"before:\n";
FOR(i,M){
cout<<" "<<bot[i]+1<<" "<<top[i]+1<<"\n";
}
cout<<"move: "<<u+1<<" -> "<<v+1<<"\nafter:\n";
ans.eb(u,v);
int a;
if(top[u]!=-1){
a=top[u];
top[u]=-1;
}else{
a=bot[u];
bot[u]=-1;
}
if(bot[v]==-1){
(x[a]/2==u?x[a]:y[a])=v*2;
bot[v]=a;
}else{
(x[a]/2==u?x[a]:y[a])=v*2+1;
top[v]=a;
}
if(bot[u]==-1){
free.pb(u);
}
FOR(i,M){
cout<<" "<<bot[i]+1<<" "<<top[i]+1<<"\n";
}
};
auto park=[&](int i,bool f){
int a=x[i]/2;
int b=y[i]/2;
assert(top[a]==-1||top[b]==-1);
if(top[b]!=-1) swap(a,b);
move(a,b);
};
auto check=[&](){
if(free.em){
cout<<-1;
exit(0);
}
};
if(2*N<=M){
auto good=[&](int a) {
return (x[a]%2==1||top[x[a]/2]==-1)&&(y[a]%2==1||top[y[a]/2]==-1);
};
vc<bool> parked(N);
FOR(i,N){
if(x[i]%2==1&&y[i]%2==1){
move(x[i]/2,free.bk);
move(y[i]/2,free.bk);
free.ppb;
}
if(x[i]/2==y[i]/2) parked[i]=1;
}
queue<int> q;
FOR(i,N){
if(!parked[i]&&good(i)){
parked[i]=1;
q.push(i);
}
}
while(!q.em){
int i=q.fr;q.pp;
int a=x[i]/2;
int b=y[i]/2;
if(top[b]!=-1) swap(a,b);
move(a,b);
if(bot[a]!=-1){
if(!parked[bot[a]]&&good(bot[a])){
parked[bot[a]]=1;
q.push(bot[a]);
}
}
}
FOR(i,N){
if(!parked[i]){
cout<<-1;
return 0;
}
}
cout<<sz(ans)<<"\n";
for(auto[x,y]:ans){
cout<<x+1<<" "<<y+1<<"\n";
}
return 0;
}
vc<bool> vis(M);
vc<vc<int>> S;
vc<vc<vc<int>>> T;
FOR(i,M){
if(vis[i]||bot[i]==top[i])continue;
int j=i,k=bot[i],f=0;
S.pb({k});
T.pb({});
while(1){
T.bk.pb({});
vis[j]=1;
k=f?bot[j]:top[j];
while(k!=bot[i]&&x[k]%2!=y[k]%2){
T.bk.bk.pb(k);
j^=(x[k]/2)^(y[k]/2);
vis[j]=1;
k=f?bot[j]:top[j];
}
if (k==bot[i])break;
S.bk.pb(k);
j^=(x[k]/2)^(y[k]/2);
f^=1;
}
}
FOR(i,sz(S)){
if (sz(S[i])==1){
check(); int t=free.bk; free.ppb;
int a=x[S[i][0]];
int b=y[S[i][0]];
if (a%2==0) swap(a,b);
move(a/2,t);
ROF(j,sz(T[i][0])) park(T[i][0][j],0);
move(b/2,t);
continue;
}
check(); int t=free.bk; free.ppb;
move(x[S[i][1]]/2,t);
move(y[S[i][1]]/2,t);
ROF(j,sz(T[i][0])) park(T[i][0][j],0);
FOR(j,sz(T[i][1])) park(T[i][1][j],0);
FFOR(j,3,sz(S[i])-1,2){
check(); int t=free.bk;free.ppb;
move(x[S[i][j]]/2,t);
move(y[S[i][j]]/2,t);
ROF(k,sz(T[i][j-1])) park(T[i][j-1][k],0);
FOR(k,sz(T[i][j])) park(T[i][j][k],0);
park(S[i][j-1],0);
}
park(S[i][0],0);
if(sz(S[i])%2){
FOR(j,sz(T[i].bk)) park(T[i].bk[j],0);
park(S[i].bk,1);
}
}
cout<<sz(ans)<<"\n";
for(auto[x,y]:ans){
cout<<x+1<<" "<<y+1<<"\n";
}
return 6/22;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2073 ms |
142844 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1000 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1000 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
980 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
