Bạn được yêu cầu giúp chẩn đoán các sơ đồ lớp để xác định các trường hợp kế thừa hình thoi (diamond inheritance). Sơ đồ lớp ví dụ sau đây minh họa tính chất của kế thừa hình thoi. Có bốn lớp: A, B, C và D. Một mũi tên trỏ từ X đến Y cho biết lớp X kế thừa từ lớp Y.

Trong sơ đồ lớp này, D kế thừa từ cả B và C, B kế thừa từ A, và C cũng kế thừa từ A. Một đường đi kế thừa từ X đến Y được định nghĩa là một chuỗi các lớp X, \(C_1, C_2, C_3, \dots, C_n\), Y trong đó X kế thừa từ \(C_1\), \(C_i\) kế thừa từ \(C_{i+1}\) với \(1 \le i \le n-1\), và \(C_n\) kế thừa từ Y. Có hai đường đi kế thừa từ D đến A trong ví dụ trên. Đường đi thứ nhất là D, B, A và đường đi thứ hai là D, C, A.

Một sơ đồ lớp được cho là chứa kế thừa hình thoi nếu tồn tại một cặp lớp X và Y sao cho có ít nhất hai đường đi kế thừa khác nhau từ X đến Y. Sơ đồ lớp ở trên là một ví dụ điển hình về kế thừa hình thoi. Nhiệm vụ của bạn là xác định xem một sơ đồ lớp cho trước có chứa kế thừa hình thoi hay không.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo, mỗi bộ mô tả một sơ đồ lớp. Dòng đầu tiên của mỗi bộ thử nghiệm cho biết số lượng lớp trong sơ đồ này, \(N\). Các lớp được đánh số từ 1 đến \(N\). \(N\) dòng tiếp theo. Dòng thứ \(i\) bắt đầu bằng một số nguyên không âm \(M_i\) cho biết số lượng lớp mà lớp \(i\) kế thừa trực tiếp. Tiếp theo là \(M_i\) số nguyên dương phân biệt, mỗi số từ 1 đến \(N\) đại diện cho các lớp đó. Bạn có thể giả định rằng:

• Nếu có một đường đi kế thừa từ X đến Y thì không có đường đi kế thừa từ Y đến X.
• Một lớp sẽ không bao giờ kế thừa từ chính nó.

Dữ liệu ra

Với mỗi sơ đồ, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là "Yes" nếu sơ đồ lớp chứa kế thừa hình thoi, ngược lại là "No".

Ràng buộc

• \(1 \le T \le 50\).
• \(0 \le M_i \le 10\).

Phân nhóm

• Test set 1 (Visible Verdict): \(1 \le N \le 50\).
• Test set 2 (Hidden Verdict): \(1 \le N \le 1,000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

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

Nguồn

Google Code Jam 2012, Vòng 1C, bài Diamond Inheritance.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.