Tiến hóa bò

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho $N$ quần thể, mỗi quần thể có một tập đặc điểm (xâu ký tự). Kiểm tra xem có tồn tại cây tiến hóa hợp lệ hay không: mỗi đặc điểm chỉ xuất hiện trên đúng một cạnh của cây (tức mỗi đặc điểm tiến hóa đúng một lần).

Cây tiến hóa hợp lệ khi và chỉ khi không có hai đặc điểm nào "giao chéo": tức không tồn tại hai đặc điểm $A, B$ sao cho đồng thời có quần thể chỉ có $A$ , quần thể chỉ có $B$ , và quần thể có cả $A$ lẫn $B$ .

Dữ liệu vào

Dòng đầu: $N$ .
$N$ dòng tiếp: mỗi dòng bắt đầu bằng $K_{i}$ , tiếp theo $K_{i}$ xâu ký tự là tên các đặc điểm.

Dữ liệu ra

In yes nếu tồn tại cây tiến hóa hợp lệ, ngược lại in no.

Ràng buộc

$2 \leq N \leq 25$
$0 \leq K_{i} \leq 25$
Mỗi xâu đặc điểm dài tối đa 20 ký tự thường.
Không có hai quần thể có cùng tập đặc điểm.

Ví dụ

Input	Output	Giải thích
4 2 spots firebreathing 0 1 flying 2 telepathic flying	yes	Không có cặp đặc điểm nào giao chéo.
7 2 yhidd rzowk 1 rzowk 1 wlrbb 2 wlrbb qbhcd 2 rzowk scdxr 1 mowfr 0	yes	Các tập đặc điểm lồng nhau hoặc rời nhau.

Bình luận

Không có bình luận tại thời điểm này.