题解：P13855 [CERC 2023] Keys

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<stack>
#define pb push_back
using namespace std;
const int N=400050;
int vis[N],n,fa[N],tmp=-1,m,stt[N],res=-1;
vector<int>g[N],t[N];
map<pair<int,int>,int>mp;
int tot=0,top=0,cnt=0;
void dfs(int x){
	// cout<<x<<" ";
    vis[x]=1;
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(vis[v]){
            if(v==1&&fa[x]!=v)tmp=x;
            continue;
        }
        fa[v]=x;
        t[x].pb(v);
        dfs(v);
    }
}
int vis2[N];
void dfs2(int x){
	if(vis2[x])return;
	vis2[x]=1;
	for(int i=0;i<g[x].size();i++){
		int v=g[x][i];
        if(v==1&&fa[x]!=v)tmp=x;
	}
    for(int i=0;i<t[x].size();i++){
        int v=t[x][i];
        dfs2(v);
    }
}
map<int,int>same;
void subsolve(){
    vector<int>v1,v2,akey;
    for(int i=0;i!=1;i=fa[i])
        v1.pb(i),akey.pb(mp[{i,fa[i]}]),stt[mp[{i,fa[i]}]]=1;
    for(int i=tmp;i!=1;i=fa[i])
        v2.pb(i);
    int key2=mp[{1,tmp}];
    stt[key2]=1;
    for(int i=1;i<=m;i++)if(stt[i]==1)cout<<i-1<<" ";
    cout<<endl;
    for(int i=1;i<=m;i++)if(stt[i]==0)cout<<i-1<<" ";
    cout<<endl;
    for(int i=1;i<v1.size();i++){
        cout<<"MOVE "<<v1[i]<<endl;
    }
    cout<<"MOVE 1\nMOVE "<<tmp<<endl;
    cout<<"DROP ";
    for(int i=0;i<akey.size();i++){
        cout<<akey[i]-1<<" ";
    }
    cout<<"\nMOVE 1\nDONE\n";
    for(int i=v2.size()-1;i>=0;i--){
        cout<<"MOVE "<<v2[i]<<endl;
    }
    cout<<"GRAB\n";
    for(int i=1;i<v2.size();i++){
        cout<<"MOVE "<<v2[i]<<endl;
    }
    cout<<"MOVE 1\n";
    for(int i=v1.size()-1;i>=0;i--){
        cout<<"MOVE "<<v1[i]<<endl;
    }
	cout<<"DONE";
}
int main(){
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        mp[{u,v}]=mp[{v,u}]=i;
        g[u].pb(v),g[v].pb(u);
    }
    dfs(1);
    if(tmp==-1){
        cout<<"No solution";
        return 0;
    }
	tmp=-1;
    for(int i=0;;i=fa[i]){
        dfs2(i);
		if(tmp!=-1){
			res=i;
			break;
		}
        if(i==1)break;
    }
	if(res==1)return subsolve(),0;
    vector<int>v1,v2,v3,keya,keya2;
    for(int i=0  ;i!=res;i=fa[i])v1.pb(i),keya .pb(mp[{i,fa[i]}]),stt[mp[{i,fa[i]}]]=1;
    for(int i=tmp;i!=res;i=fa[i])v2.pb(i);
    for(int i=res;i!=1  ;i=fa[i])v3.pb(i),keya2.pb(mp[{i,fa[i]}]),stt[mp[{i,fa[i]}]]=1;
    for(int i=1;i<=m;i++)if(stt[i]==1)cout<<i-1<<" ";
    cout<<endl;
    for(int i=1;i<=m;i++)if(stt[i]==0)cout<<i-1<<" ";
    cout<<endl;	
	for(int i=0;i<v1.size();i++){
		cout<<"MOVE "<<fa[v1[i]]<<endl;
	}
	if(keya.size())
	cout<<"DROP ";
	for(int i=0;i<keya.size();i++){
		cout<<keya[i]-1<<" ";
	}
	
	if(keya.size())cout<<endl;
	for(int i=0;i<v3.size();i++){
		cout<<"MOVE "<<fa[v3[i]]<<endl;
	}
	cout<<"DONE\n";
	for(int i=0;i<v2.size();i++){
		cout<<"MOVE "<<v2[i]<<endl;
	}
	cout<<"MOVE "<<res<<endl;
	cout<<"GRAB"<<endl;
	for(int i=v1.size()-1;i>=0;i--){
		cout<<"MOVE "<<v1[i]<<endl;
	}
	cout<<"DONE\n";
}