다이아몬드 상속

클래스 다이어그램을 진단하여 다이아몬드 상속이 발생한 경우를 식별하는 일을 도와야 한다. 다음 클래스 다이어그램의 예는 다이아몬드 상속의 성질을 보여 준다. A, B, C, D라는 네 개의 클래스가 있다. X에서 Y를 향하는 화살표는 클래스 X가 클래스 Y를 상속한다는 것을 나타낸다.

이 클래스 다이어그램에서 D는 B와 C를 모두 상속하고, B는 A를 상속하며, C도 A를 상속한다. X에서 Y로의 상속 경로는 클래스들의 수열 X, $C_{1}$, $C_{2}$, $C_{3}$, ..., $C_{n}$, Y로 정의된다. 여기서 X는 $C_{1}$을 상속하고, 1 ≤ i ≤ n - 1에 대해 $C_{i}$은 $C_{i + 1}$을 상속하며, $C_{n}$은 Y를 상속한다. 위 예에는 D에서 A로 가는 상속 경로가 두 개 있다. 첫 번째 경로는 D, B, A이고 두 번째 경로는 D, C, A이다.

서로 다른 두 클래스 X와 Y가 존재하여 X에서 Y로 가는 서로 다른 상속 경로가 적어도 두 개 있다면, 그 클래스 다이어그램은 다이아몬드 상속을 포함한다고 한다. 위 클래스 다이어그램은 다이아몬드 상속의 전형적인 예이다. 주어진 클래스 다이어그램이 다이아몬드 상속을 포함하는지 여부를 판별해야 한다.

제한

메모리 제한: 1GB. 테스트 세트당 시간 제한: 40초. 1 ≤ T ≤ 50. 0 ≤ $M_{i}$ ≤ 10.

테스트 세트 1 (Visible Verdict)

1 ≤ N ≤ 50.

테스트 세트 2 (Hidden Verdict)

1 ≤ N ≤ 1,000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 각각 클래스 다이어그램 하나를 나타내는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 이 다이어그램의 클래스 수 N이 주어진다. 클래스에는 1부터 N까지 번호가 매겨져 있다. 이어서 N개의 줄이 주어진다. $i^{th}$번째 줄은 음이 아닌 정수 $M_{i}$로 시작하며, 이는 클래스 i가 상속하는 클래스의 수를 나타낸다. 이어서 각각 1부터 N까지의 정수인 서로 다른 양의 정수 $M_{i}$개가 주어지며, 이들은 클래스 i가 상속하는 클래스들을 나타낸다. 다음을 가정해도 좋다.

• X에서 Y로 가는 상속 경로가 있다면 Y에서 X로 가는 상속 경로는 없다.

• 클래스는 절대로 자기 자신을 상속하지 않는다.

각 다이어그램마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, 클래스 다이어그램이 다이아몬드 상속을 포함하면 y는 "Yes"이며, 그렇지 않으면 "No"이다.