Description：

已知 $n$ 对夫妻的婚姻状况，称第 $i$ 对夫妻的男方为 $B_i$ ，女方为 $G_i$ 。某男 $B_i$ 与某女 $G_j$ 曾经交往过，若在 $B_i$ 和 $G_i$ 离婚的前提下，这 $2n$ 个人最终依然能够结合成 $n$ 对情侣，那么我们称婚姻 $i$ 为不安全的，否则婚姻 $i$ 就是安全的。

$1\le N \le 4000$ $0 \le M \le 20000$

Solution：

如果是夫妻，则男连女，如果曾经交往过，则女连男，跑 $tarjan$ 判断是否有夫妻在同一强连通分量中，如果在，那么说明关系形成了环，那么交换边也能成立，所以不安全。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<map>

#include<cstring>

using namespace std;

int n,m;

map<string,int> p;

int cnt = 0;

int tr(string k)

{

    if(p[k] == 0)return (p[k] = ++cnt);

    else return p[k];

}

#define MAXN 10010

string sa[MAXN],sb[MAXN];

int dfn[MAXN],low[MAXN],tot = 0;

stack<int> s;

bool v[MAXN];

int scc = 0,ins[MAXN];

struct edge

{

    int to,nxt;

}e[500010];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    return;

}

void tarjan(int k)

{

    dfn[k] = low[k] = ++tot;

    v[k] = true;s.push(k);

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(dfn[e[i].to] == 0)

        {

            tarjan(e[i].to);

            low[k] = min(low[k],low[e[i].to]);

        }

        else if(v[e[i].to])

        {

            low[k] = min(low[k],dfn[e[i].to]);

        }

    }

    if(low[k] == dfn[k])

    {

        int t;

        ++scc;

        do

        {

            t = s.top();s.pop();

            ins[t] = scc;v[t] = false;

        }while(t != k);

    }

    return;

}

int main()

{

    scanf("%d",&n);

    string a,b;

    for(int i = 1;i <= n;++i)

    {

        cin >> sa[i] >> sb[i];

        add(tr(sa[i]),tr(sb[i]));

    }

    scanf("%d",&m);

    for(int i = 1;i <= m;++i)

    {

        cin >> a >> b;

        add(tr(b),tr(a));

    }

    for(int i = 1;i <= cnt;++i)

    {

        if(dfn[i] == 0)tarjan(i);

    }

    for(int i = 1;i <= n;++i)

    {

        if(ins[tr(sa[i])] == ins[tr(sb[i])])puts("Unsafe");

        else puts("Safe");

    }

    return 0;

}