Lisa

问题在于环，显然。

但是怎样建图才能把环搞出来呢？不能建无向图，而且男女要交错

那就一种情况男女，另一种女男

然后就是tarjan的事情了.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<stack>
using namespace std;
stack<int> s;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int dfn[1000001];
int head[1000001];
int p;
int n;
string sss,ss;
map<string,int> m;
string num[1000001];
int low[1000001];
int id;
int cnt;
int mm;
int vis[1000001];
int be[1000001];
int nu;
struct e{
    int to;
    int ne;
    int v;
}ed[2000001];
void add(int f,int to){
    ed[++p].to=to;
    ed[p].ne=head[f];
    head[f]=p;
//  ed[p].v=v;
    return ;
}
pair<int,int> pp[1000001];
void dfs(int now){
    dfn[now]=low[now]=++id;
//  cout<<now<<endl;
    s.push(now);
    vis[now]=1;
    for(int i=head[now];i;i=ed[i].ne){
        int v=ed[i].to;
        if(!dfn[v]){
            dfs(v);
            low[now]=min(low[now],low[v]);
        }else{
            if(vis[v])
            low[now]=min(dfn[v],low[now]);
        }
    }
    if(low[now]==dfn[now]){
        nu++;
        //s.pop();
        //if(!s.empty())
        be[s.top()]=nu;
        vis[s.top()]=0;
        //s.pop();
        while(s.top()!=now){
            be[s.top()]=nu;
            vis[s.top()]=0;
            s.pop();
        }
        vis[now]=0; 
        be[now]=nu;
        if(!s.empty())
        s.pop();    
    }
}
int ans;
int main(){
    read(n);
    for(int i=1;i<=n;++i){
        cin>>sss>>ss;
        m[sss]=++cnt;
        m[ss]=++cnt;
        add(m[sss],m[ss]);
        pp[i].first=m[sss];
        pp[i].second=m[ss];
    }
    read(mm);

    for(int i=1;i<=mm;++i){
        cin>>sss>>ss;
        add(m[ss],m[sss]);
    }
    for(int i=1;i<=cnt;++i){
        if(!dfn[i]){
            dfs(i);
        }
    }
    for(int i=1;i<=n;++i){
        if(be[pp[i].first]==be[pp[i].second]){
            printf("Unsafe\n");
        }else{
            printf("Safe\n");
        }
    }
    return 0;
}