记录编号	437917	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]稳定婚姻	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.237 s
提交时间	2017-08-14 21:11:07	内存使用	0.32 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e;
	edge *n;
	edge():e(0),n(NULL){}
}a[40005],*pre[8005];
int tot;
inline void insert(int s,int e){
	a[++tot].e=e;
	a[tot].n=pre[s];
	pre[s]=&a[tot];
}
int n,m;
char s1[10],s2[10];
map<string,int>ma;
int cnt,top,qlt;
int dfn[8005],low[8005],sta[8005],bl[8005];
bool vis[8005];
inline void tarjan(int u){
	dfn[u]=low[u]=++cnt;
	sta[++top]=u;
	vis[u]=1;
	for(edge *i=pre[u];i;i=i->n){
		int e(i->e);
		if(!dfn[e]){
			tarjan(e);
			low[u]=min(low[u],low[e]);
		}
		else
			if(vis[e])
				low[u]=min(low[u],dfn[e]);
	}
	if(low[u]==dfn[u]){
		int tmp;
		++qlt;
		while(1){
			tmp=sta[top--];
			vis[tmp]=0;
			bl[tmp]=qlt;
			if(tmp==u)
				break;
		}
	}
}
inline int gg(){
	freopen("marriage.in","r",stdin);
	freopen("marriage.out","w",stdout);
	memset(pre,NULL,sizeof(pre));
	n=read();
	for(int i=1;i<=n;++i){
		scanf("%s%s",s1,s2);
		insert((i<<1)-1,i<<1);
		ma[s1]=(i<<1)-1,ma[s2]=i<<1;
	}
	m=read();
	for(int i=1;i<=m;++i){
		scanf("%s%s",s1,s2);
		insert(ma[s2],ma[s1]);
	}
	for(int i=1;i<=(n<<1);++i)
		if(!dfn[i])
			tarjan(i);
	for(int i=1;i<=n;++i){
		if(bl[(i<<1)-1]==bl[i<<1])
			puts("Unsafe");
		else
			puts("Safe");
	}
	return 0;
}
int K(gg());
int main(){;}