记录编号	253303	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]稳定婚姻	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.467 s
提交时间	2016-04-21 21:25:59	内存使用	0.70 MiB

#include <cstdio>
#include <iostream>
#include <map>

using namespace std;

map<string,int>ma;
int n,m;
struct HEOI
{
	int b;
	int x;
}c[30000];
int d[8010],l[8010],p,st[8010],tp;
int s[8010],block,bl[8010];
int ll,h[8010];
bool b[8010];

inline void gj(int a,int b)
{
	//printf("%d %d\n",a,b);
	c[++ll]=(HEOI){b,h[a]};
//	printf("%d\n",b);
	h[a]=ll;
	return;
}

void gt(int a)
{
	//printf("O%d\n",a);
//	if(a>4)
	//    while(1);
	st[++tp]=a;
	d[a]=l[a]=++p;
	b[a]=1;
	for(int i=h[a];i;i=c[i].x)
	{
		int u=c[i].b;
		if(d[u]==0)
		{
			gt(u);
			if(l[a]>l[u])
			    l[a]=l[u];
		}
		else
		    if(b[u])
		        if(l[a]>d[u])
		            l[a]=d[u];
	}
	if(d[a]==l[a])
	{
		++block;
		while(tp)
		{
			int o=st[tp--];
			b[o]=0;
			++s[block];
			bl[o]=block;
			if(o==a)
			    break;
		}
	}
	return ;
}
int main()
{
	freopen("marriage.in","r",stdin);
	freopen("marriage.out","w",stdout);
	int l=0;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string m1,m2;
		cin>>m1>>m2;
		ma[m1]=++l;
		ma[m2]=++l;
		gj(l,l-1);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		string m1,m2;
		cin>>m1>>m2;
		int a=ma[m1],b=ma[m2];
		//if(b==a+1)
		//    while(1);
		gj(a,b);
	}
	//while(1);
	for(int i=1;i<=l;i++)
	    if(d[i]==0)
	    {
	//printf("G");
		//	printf("I%d\n",i);
	        gt(i);
	    }
	for(int i=1;i<=l;i+=2)
	{
	    if(s[bl[i]]>1)
	        puts("Unsafe");
		else
		    puts("Safe");
	}
}