"... so forward this to ten other people, to prove that you believe the emperor has new clothes."

Aren't those sorts of emails annoying?

Martians get those sorts of emails too, but they have an innovative way of dealing with them. Instead of just forwarding them willy-nilly, or not at all, they each pick one other person they know to email those things to every time - exactly one, no less, no more (and never themselves). Now, the Martian clan chieftain wants to get an email to start going around, but he stubbornly only wants to send one email. Being the chieftain, he managed to find out who forwards emails to whom, and he wants to know: which Martian should he send it to maximize the number of Martians that see it?

Input

The first line of input will contain T (≤ 20) denoting the number of cases.

Each case starts with a line containing an integer N (2 ≤ N ≤ 50000) denoting the number of Martians in the community. Each of the next N lines contains two integers: u v (1 ≤ u, v ≤ N, u ≠ v) meaning that Martian u forwards email to Martian v.

Output

For each case, print the case number and an integer m, where m is the Martian that the chieftain should send the initial email to. If there is more than one correct answer, output the smallest number.

3

3

1 2

2 3

3 1

4

1 2

2 1

4 3

3 2

5

1 2

2 1

5 3

3 4

4 5

Case 1: 1

Case 2: 4

Case 3: 3

Problem Setter: Wheeler, Zachary J, Special Thanks: Jane Alam Jan

就用 SCC 進行縮點

#include <stdio.h>
#define maxN 50005
int min(int x, int y) {
    return x < y ? x : y;
}
int used[maxN], dp[maxN], send[maxN];
int in_stk[maxN], stk[maxN], stkIdx;
int vfind[maxN], fdIdx;
int lead[maxN];
int dfs(int nd) {
    used[nd] = in_stk[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++fdIdx;
    int mn = vfind[nd];
    if(!used[send[nd]])
        mn = min(mn, dfs(send[nd]));
    if(in_stk[send[nd]])
        mn = min(mn, vfind[send[nd]]);
    if(mn == vfind[nd]) {
        int cnt = -1;
        do {
            lead[stk[stkIdx]] = nd;
            in_stk[stk[stkIdx]] = 0;
            cnt++;
        } while(stk[stkIdx--] != nd);
        if(cnt > 0)
            dp[nd] += cnt;
        else
            dp[nd] += dp[lead[send[nd]]];
    }
    return mn;
}
int main() {
    int n, t, i, j;
    int cases = 0;

    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int u, v;
        for(i = 1; i <= n; i++) {
            scanf("%d %d", &u, &v);
            send[u] = v;
            used[i] = in_stk[i] = 0;
            dp[i] = 1;
            lead[i] = i;
        }
        int ans = -1, an;
        for(i = 1; i <= n; i++) {
            if(!used[i]) {
                fdIdx = 0, stkIdx = -1;
                dfs(i);
            }
        }
        for(i = 1; i <= n; i++) {
            if(dp[i] > ans)
                ans = dp[i], an = i;
        }
        printf("Case %d: %d\n", ++cases, an);
    }
    return 0;
}