记录编号	580867	评测结果	AAAAAAAAWWWWAAAAWWWW
题目名称	[CSP 2022S]星战	最终得分	60
用户昵称	空条承太郎&	是否通过	未通过
代码语言	C++	运行时间	12.752 s
提交时间	2023-07-27 11:05:50	内存使用	249.08 MiB

#include<bits/stdc++.h>
using namespace std;
int nm[5010][5010],n,m,q,dy[5010][5010],top1[5010],jl[5010],dx[5010][5010],top2[5010];
int dfs(int x){
    int ans=0;
    if(jl[x]==1){
        ans=1;
        return ans;
    }
    for(int i=1;i<=n;i++){
        if(nm[x][i]==1){
            jl[i]=1;
            ans=dfs(i);
            jl[i]=0;
        }
    }
    return ans;
}
int main(){
    freopen("csp2022_galaxy.in","r",stdin);
    freopen("csp2022_galaxy.out","w",stdout);
    cin>>n>>m;
    if(n>1010){
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
        }
        cin>>q;
        while(q--){
            cout<<"NO"<<endl;
        }
        return 0;
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        nm[x][y]=1;
        top1[y]++;
        dy[y][top1[y]]=x;
        top2[x]++;
        dx[x][top2[x]]=y;
    }
    cin>>q;
    while(q--){
        int t,u,v,xb,ans,res=1;
        cin>>t;
        if(t==1){
            cin>>u>>v;
            nm[u][v]=-1;
            for(int i=1;i<=top2[u];i++){
                if(dx[u][i]==v){
                    xb=i;
                    break;
                }
            }
            for(int i=xb+1;i<=top2[u];i++){
                dx[u][i]=dx[u][i-1];
            }
            top2[u]--;
        }
        if(t==3){
            cin>>u>>v;
            nm[u][v]=1;
            top2[u]++;
            dx[u][top2[u]]=v;
        }
        if(t==2){
            cin>>u;
            int xb;
            for(int i=1;i<=n;i++){
                if(nm[i][u]==1){
                  top1[u]=0;
                  nm[i][u]=-1;
                  for(int j=1;j<=top2[i];j++){
                    if(dx[i][j]==u){
                    xb=j;
                    break;
                    }
                  }
                  for(int j=xb+1;j<=top2[i];j++){
                     dx[i][j]=dx[i][j-1];
                   }
                  top2[i]--;
                }
            }
        }
        if(t==4){
            cin>>u;
            int xb;
            for(int i=1;i<=n;i++){
                if(nm[i][u]==-1){
                  top1[u]++;
                  nm[i][u]=1;
                  top2[i]++;
                  dx[i][top2[i]]=u;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(top2[i]<1||top2[i]>1){
                res=0;
                break;
            }
            jl[i]=1;
            ans=dfs(i);
            jl[i]=0;
        }
        if(res==1){
            if(ans==1){
                cout<<"YES"<<endl;
                continue;
            }
        }
        cout<<"NO"<<endl;
    }
    return 0;
}