二分图匹配45超时求调

#include<bits/stdc++.h>
using namespace std;
int n,m,num,head[4000],cp[5000],flag[5000],pd[5000];
string G,B;
map<string,int>p;
struct edge{int next,to;}g[30000];
void add(int u,int v){g[++num]=(edge){head[u],v};head[u]=num;}
bool dfs(int u,int t,int k){
	if(pd[u]==t)	return 0;
	pd[u]=t;
	for(int i=head[u];i;i=g[i].next){
		if(i==k)	continue;
		int v=g[i].to;
		if(!cp[v]||dfs(cp[v],t,k)){
			cp[v]=u;
			return 1;
		}
	}
	return 0;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>G>>B;
		p[G]=i;
		p[B]=i;
		add(i,i);
		flag[i]=num;
	}
	cin>>m;
	while(m--)	cin>>G>>B,add(p[G],p[B]);
	for(int i=1;i<=n;++i){
		memset(cp,0,sizeof(cp));
		memset(pd,0,sizeof(pd));
		for(int j=1;j<=n;++j)
			if(!dfs(j,j,flag[i])){
				puts("Safe");
				goto nxt;
			}
		puts("Unsafe");
		nxt:;
	}
	return 0;
}