One of my friends is always drunk. So, sometimes I get a bit confused whether he is drunk or not. So, one day I was talking to him, about his drinks! He began to describe his way of drinking. So, let me share his ideas a bit. I am expressing in my words.
There are many kinds of drinks, which he used to take. But there are some rules; there are some drinks that have some pre requisites. Suppose if you want to take wine, you should have taken soda, water before it. That’s why to get real drunk is not that easy.
Now given the name of some drinks! And the prerequisites of the drinks, you have to say that whether it’s possible to get drunk or not. To get drunk, a person should take all the drinks.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.
Each case starts with an integer m (1 ≤ m ≤ 10000). Each of the next m lines will contain two names each in the format a b, denoting that you must have a before having b. The names will contain at most 10 characters with no blanks.

Output

For each case, print the case number and ‘Yes’ or ‘No’, depending on whether it’s possible to get drunk or not.

题意：

多组数据，给你一些关系，如样例中soda wine，表示你要用wine则要先用soda，每组数据都会有多个这样的关系，问你是否能确定从哪里开始使得方案唯一。如数据中第二组数据：用wine之前要先用soda或water，而用water之前要先用wine，那么就不能确定是先用water还是wine。所以答案不合法，输出No。

题解：

我们不难看出这是一张有向图，然后其不合法的状态就是有环的存在，所以我们用tarjan判一下强连通分量的数量即可。
注意：图不一定联通，我就这样被卡了好多次。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int fst[23333], nxt[23333], tot = 0, ssum = 0, cnt = 0, scc = 0;
bool used[23333];
int dfn[23333], low[23333], stack[23333];
int size[23333];
struct qer
{
    int from, to;
}es[23333];
map <string, int> num;
void build (int f, int t)
{
    es[++tot] = (qer){f, t};
    nxt[tot] = fst[f];
    fst[f] = tot;
}
inline void dfs(int x)
{
    dfn[x] = low[x] = ++tot;
    stack[++ssum] = x;
    used[x] = 1;
    for (int i = fst[x]; i; i = nxt[i])
    {
        int u = es[i].to;
        if (!dfn[u])
        {
            dfs(u);
            low[u] = min(low[u], low[x]);
        }
        else if (used[u])
            low[x] = min(low[x], dfn[u]);
    }
    if (dfn[x] == low[x])
    {
        scc++;
        cnt++;
        while (1)
        {
            size[cnt]++;
            used[stack[ssum]] = 0;
            ssum--;
            if (stack[ssum+1] == x)
                break;
        }
    }
}
void init()
{
    memset(used, 0, sizeof(used));
    memset(stack, 0, sizeof(stack));
    tot = 0, cnt = 0, ssum = 0, scc = 0;
    memset(fst, 0, sizeof(fst));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(size, 0, sizeof(size));
    num.clear();
}
int main()
{
    int T;
    cin >> T;
    for (int sss = 1; sss <= T; sss++)
    {
        init();
        int ls = 0;
        int n;
        cin >> n;
        string a, b;
        for (int i = 1; i <= n; i++)
        {
            cin >> a >> b;
            if (!num[a]) ls++, num[a] = ls;
            if (!num[b]) ls++, num[b] = ls;
            build (num[a], num[b]);
        }
        tot = 0;
        printf("Case %d: ", sss);
        for (int i = 1; i <= ls; i++)
            if (!dfn[i])
                dfs(i);
        if (scc < ls)
            puts("No");
        else
            puts("Yes");
    }
    return 0;
}
/*
2
3
a b
b c
c a
2
a b
d c
1
4
a b
b c
a d
d c
YES
*/