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年，在過(guò)去的一千年里發(fā)生了不計(jì)其數(shù)的牛類(lèi)進(jìn)化，產(chǎn)生了具有各種有趣特性的奶牛。

牛類(lèi)進(jìn)化的記錄可以用一棵樹(shù)來(lái)表示，起源是位于樹(shù)根位置的沒(méi)有特殊特性的奶牛。樹(shù)上每一個(gè)產(chǎn)生后代的結(jié)點(diǎn)，有可能所有的奶牛都進(jìn)化出了一種新的特性（比如說(shuō)噴火（fire breathing），如下圖所示，其中所有斑點(diǎn)（spots）奶牛最后都能?chē)娀穑蛘呤悄膛７N群產(chǎn)生了分支進(jìn)化，其中有些進(jìn)化出了新的特性（比如，飛（flying）），有的沒(méi)有。

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

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

輸入樣例：

4
2 spots firebreathing
0
1 flying
2 telepathic flying

輸出樣例：

yes

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

供題：Brian Dean