USACO 2019 US Open Contest, Bronze Problem 3 Cow Evolution

It is the year 3019, and a surprising amount of bovine evolution has transpired in the past thousand years, resulting in cows with all sorts of interesting features.

The bovine evolutionary record can be described?as?a tree, starting with a basic ancestral cow at the root with no special features. At each descendant?level?in the tree, either all cows evolve a new feature (such?as?fire breathing, below, where all cows with spots ended up breathing fire), or there is a divergent split in the bovine population where some of the cows evolve a new feature (e.g., flying) and some do not.

The leaves at the bottom of the tree indicate all the resulting sub-populations of cows in the year 3019. No leaves (sub-populations) contain identical sets of features. For example, sub-population #1 contains cows with no special features, while sub-population #3 contains telepathic flying cows. Sub-population #2, by contrast, has flying cows that are not telepathic. Sub-population #3 is unique in its combination of flying and telepathic cows.

An evolutionary tree like the one above is called "proper" if each newly evolved feature originates in exactly one edge of the tree (e.g., it evolved into being at a single point in history). For example, a tree would not be proper if spots evolved into being in two separate branches. Given a description of the sub-populations of cows in the year 3019, please determine if these can be described by a proper evolutionary tree.

SAMPLE INPUT:

4
2 spots firebreathing
0
1 flying
2 telepathic flying

SAMPLE OUTPUT:

yes

This example input corresponds to the proper tree shown in the diagram above.

Problem credits: Brian Dean

---

中文版

現(xiàn)在是3019年，在過去的一千年里發(fā)生了不計其數(shù)的牛類進(jìn)化，產(chǎn)生了具有各種有趣特性的奶牛。

牛類進(jìn)化的記錄可以用一棵樹來表示，起源是位于樹根位置的沒有特殊特性的奶牛。樹上每一個產(chǎn)生后代的結(jié)點，有可能所有的奶牛都進(jìn)化出了一種新的特性（比如說噴火（fire breathing），如下圖所示，其中所有斑點（spots）奶牛最后都能噴火），或者是奶牛種群產(chǎn)生了分支進(jìn)化，其中有些進(jìn)化出了新的特性（比如，飛（flying）），有的沒有。

樹底部的葉結(jié)點表示3019年所有產(chǎn)生的奶牛的子種群。沒有不同的葉結(jié)點（子種群）具有完全相同的一組特性。例如，子種群#1是沒有特殊特性的奶牛，子種群#3是能夠心靈感應(yīng)的（telepathic）會飛的奶牛。相比之下，子種群#2是會飛但不能心靈感應(yīng)的奶牛。子種群#3是唯一既會飛又會心靈感應(yīng)的。

像上圖這樣每一種進(jìn)化出的新特性都恰好在樹中的一條邊上產(chǎn)生（也就是說，在整個進(jìn)化歷史中僅在一個時間點產(chǎn)生），這樣的進(jìn)化樹被稱為是“合法的”。例如，如果斑點這一特性在兩個不同分支中均進(jìn)化產(chǎn)生，這棵進(jìn)化樹就不是合法的。給定3019年奶牛子種群的描述，請判斷是否這可以由一棵合法的進(jìn)化樹所解釋。

輸入樣例：

4
2 spots firebreathing
0
1 flying
2 telepathic flying

輸出樣例：

yes

這個輸入樣例與上圖所示的合法進(jìn)化樹一致。

供題：Brian Dean