diamonddebai

Bạn được yêu cầu giúp chẩn đoán sơ đồ lớp để xác định các trường hợp thừa kế kim cương. Sơ đồ lớp mẫu sau minh họa đặc tính thừa kế kim cương. Có bốn lớp: A, B, C và D. Một mũi tên chỉ từ X đến Y chỉ ra rằng lớp X thừa kế 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. Đường dẫn 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 , ..., C n , Y trong đó X kế thừa từ C 1 , C i  kế thừa từ C i + 1  với 1 ≤ i ≤ n - 1 và C n kế thừa từ Y. Có hai đường dẫn kế thừa từ D đến A trong ví dụ trên. Đường dẫn đầu tiên là D, B, A và đường dẫn thứ hai là D, C, A.

Một sơ đồ lớp được cho là chứa một sự kế thừa kim cương nếu tồn tại một cặp lớp X và Y sao cho có ít nhất hai đường dẫn 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ề sự kế thừa kim cương. Nhiệm vụ của bạn là xác định xem một sơ đồ lớp nhất định có chứa sự kế thừa kim cương hay không.

Đầu vào

Dòng đầu tiên của đầu vào đưa ra số lượng các trường hợp thử nghiệm,  T. T trường hợp   thử nghiệm theo sau, mỗi trường hợp chỉ định một sơ đồ lớp. Dòng đầu tiên của mỗi trường hợp thử nghiệm đưa ra số lượng các lớp trong sơ đồ này,  N. Các lớp được đánh số từ 1 đến  N. N  dòng theo sau. Dòng thứ i bắt đầu   bằng một số nguyên không âm  M i  biểu thị số lượng các lớp mà lớp  i  kế thừa từ đó. Tiếp theo là  M i  các số nguyên dương khác nhau, mỗi số nguyên từ 1 đến  N  biểu thị các lớp đó. Bạn có thể giả sử rằng:

Nếu có đường dẫn thừa kế từ X đến Y thì không có đường dẫn thừa kế từ Y đến X.

Một lớp sẽ không bao giờ kế thừa từ chính nó.

Đầu ra

Đối với mỗi sơ đồ, hãy xuất ra một dòng chứa "Trường hợp #x: y", trong đó x là số trường hợp (bắt đầu từ 1) và y là "Có" nếu sơ đồ lớp chứa dạng kế thừa hình thoi, nếu không thì là "Không".

Hạn mức
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