# Diamond

quoc14
c_cpp
20 days ago
3.9 kB
6
Indexable
Never
DFS and BFS
```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;
}
```