Diamond

Level 4
Diamond
You are asked to help diagnose class diagrams to identify instances of diamond inheritance. The following example class diagram illustrates the property of diamond inheritance. There are four classes: A, B, C and D. An arrow pointing from X to Y indicates that class X inherits from class Y.


In this class diagram, D inherits from both B and C, B inherits from A, and C also inherits from A. An inheritance path from X to Y is defined as a sequence of classes X, C1, C2, C3, ..., Cn, Y where X inherits from C1, Ci inherits from Ci + 1 for 1 ≤ i ≤ n - 1, and Cn inherits from Y. There are two inheritance paths from D to A in the example above. The first path is D, B, A and the second path is D, C, A.

A class diagram is said to contain a diamond inheritance if there exists a pair of classes X and Y such that there are at least two different inheritance paths from X to Y. The above class diagram is a classic example of diamond inheritance. Your task is to determine whether or not a given class diagram contains a diamond inheritance.

Input

The first line of the input gives the number of test cases, T. T test cases follow, each specifies a class diagram. The first line of each test case gives the number of classes in this diagram, N. The classes are numbered from 1 to N. N lines follow. The ith line starts with a non-negative integer Mi indicating the number of classes that class i inherits from. This is followed by Mi distinct positive integers each from 1 to N representing those classes. You may assume that:

If there is an inheritance path from X to Y then there is no inheritance path from Y to X.

A class will never inherit from itself.

Output

For each diagram, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is "Yes" if the class diagram contains a diamond inheritance, "No" otherwise.

Limits

1 ≤ T ≤ 50.
0 ≤ Mi ≤ 10.

Small dataset

1 ≤ N ≤ 50.

Large dataset

1 ≤ N ≤ 1,000.

Sample

Input   

3
3
1 2
1 3
0
5
2 2 3
1 4
1 5
1 5
0
3
2 2 3
1 3
0 

Output

Case #1 
No
Case #2 
Yes
Case #3 
Yes


Case #1
No
Case #2
Yes
Case #3
Yes
Case #4
No
Case #5
No
Case #6
Yes
Case #7
No
Case #8
Yes
Case #9
Yes
Case #10
Yes
Case #11
No
Case #12
Yes
Case #13
Yes
Case #14
No
Case #15
No
Case #16
Yes
Case #17
No
Case #18
Yes
Case #19
Yes
Case #20
Yes
Case #21
Yes
Case #22
Yes
Case #23
Yes
Case #24
Yes
Case #25
Yes
Case #26
Yes
Case #27
Yes
Case #28
Yes
Case #29
Yes
Case #30
Yes
Case #31
Yes
Case #32
Yes
Case #33
No
Case #34
Yes
Case #35
No
Case #36
No
Case #37
Yes
Case #38
Yes
Case #39
No
Case #40
Yes
Case #41
No
Case #42
Yes
Case #43
No
Case #44
No
Case #45
No
Case #46
No
Case #47
No
Case #48
No
Case #49
No
Case #50
No


#include <iostream>
using namespace std;

int T, n, m, vCnt;
bool result;
int mp[1001][1001], cnt[1001], vs[1001];

void dfs(int v){
	if(result) return;
	for(int i = 0; i < cnt[v]; i++){
		if(vs[mp[v][i]] == 0){
			vs[mp[v][i]]++;
			dfs(mp[v][i]);
		} else {
			result = true;
			break;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	cin >> T;
	
	for(int tc = 1; tc <= T; tc++){
		// Input
		cin >> n;
		for(int i = 1; i <= n; i++){
			cin >> cnt[i];
			for(int j = 0; j < cnt[i]; j++){
				cin >> mp[i][j];
			}
		}

		// Initial
		result = false;

		// Solve Problem
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <=n; j++) vs[j] = 0;
			for(int j = 0; j < cnt[i]; j++){
				if(vs[mp[i][j]] >= 1){
					result = true;
					break;
				} else{
					vs[i]++, vs[mp[i][j]]++;
					dfs(mp[i][j]);
				}
			}
			if(result) break;
		}
		
		// Output
		cout << "Case #" << tc << endl << (result ? "Yes" : "No") << endl;
	}

	return 0;
 }