这个题面很有意思，像我这样的菜鸡，完全不需考虑婚姻的稳定 性 问题。
tarjan裸题，直接讲算法吧：
原配夫妻之间分别连一条边，小情人之间反向连边。
这时候我们会发现一个性质，如果婚姻稳定，那么夫妻之间肯定不在一个强连通分量中，反之，在一个强连通分量中的夫妻就是Unsafe的。
代码：
#include <bits/stdc++.h>
using namespace std;
stack <int> ss;
const int N=200010;
map <string,int> mp;
int n,m,s[N][2],o[N],cnt;
int low[N],dfn[N],dfscnt,scc,sccno[N];
void add(int x,int y)
{
s[++cnt][0]=y;
s[cnt][1]=o[x];
o[x]=cnt;
}
void tarjan(int x)
{
ss.push(x);
low[x]=dfn[x]=++dfscnt;
for (int i=o[x];i;i=s[i][1]) {
if (!dfn[s[i][0]]) {
tarjan(s[i][0]);
low[x]=min(low[x],low[s[i][0]]);
}
else if (!sccno[s[i][0]])
low[x]=min(low[x],dfn[s[i][0]]);
}
if (dfn[x]==low[x]) {
scc++;
while (1) {
int y=ss.top();
sccno[y]=scc;
ss.pop();
if (x==y) break;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;string a,b;
for (int i=1;i<=n;i++) {
cin>>a>>b;
mp[a]=i;
mp[b]=i+n;
add(i,i+n);
}
cin>>m;
for (int i=1;i<=m;i++) {
cin>>a>>b;
add(mp[b],mp[a]);
}
m=n<<1;
for (int i=1;i<=m;i++)
if (!dfn[i])
tarjan(i);
for (int i=1;i<=n;i++)
if (sccno[i]==sccno[i+n])
cout<<"Unsafe\n";
else cout<<"Safe\n";
return 0;
}