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.
INPUT FORMAT (file evolution.in):
The first line of input contains the number of sub-populations, NN (2≤N≤252≤N≤25). Each of the next NN lines describes a sub-population. The line starts with an integer KK (0≤K≤250≤K≤25), then KK characteristics of all the cows in that sub-population. Characteristics are strings of up to 20 lowercase characters (a..z). No two sub-populations have exactly the same characteristics.
OUTPUT FORMAT (file evolution.out):
Please output "yes" if it is possible to form a proper evolutionary tree explaining the origin of these sub-populations, and "no" otherwise.
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
中文版
现在是3019年,在过去的一千年里发生了不计其数的牛类进化,产生了具有各种有趣特性的奶牛。
牛类进化的记录可以用一棵树来表示,起源是位于树根位置的没有特殊特性的奶牛。树上每一个产生后代的结点,有可能所有的奶牛都进化出了一种新的特性(比如说喷火(fire breathing),如下图所示,其中所有斑点(spots)奶牛最后都能喷火),或者是奶牛种群产生了分支进化,其中有些进化出了新的特性(比如,飞(flying)),有的没有。
树底部的叶结点表示3019年所有产生的奶牛的子种群。没有不同的叶结点(子种群)具有完全相同的一组特性。例如,子种群#1是没有特殊特性的奶牛,子种群#3是能够心灵感应的(telepathic)会飞的奶牛。相比之下,子种群#2是会飞但不能心灵感应的奶牛。子种群#3是唯一既会飞又会心灵感应的。
像上图这样每一种进化出的新特性都恰好在树中的一条边上产生(也就是说,在整个进化历史中仅在一个时间点产生),这样的进化树被称为是“合法的”。例如,如果斑点这一特性在两个不同分支中均进化产生,这棵进化树就不是合法的。给定3019年奶牛子种群的描述,请判断是否这可以由一棵合法的进化树所解释。
输入格式(文件名:evolution.in):
输入的第一行包含子种群的数量NN(2≤N≤252≤N≤25)。以下NN行每行描述一个子种群。每行包含一个整数KK (0≤K≤250≤K≤25),之后是KK个该子种群奶牛所拥有的特性。特性是由至多20个小写字母(a..z)组成的字符串。没有两个子种群拥有完全相同的特性。
输出格式(文件名:evolution.out):
如果可能构造一棵可以解释所有子种群产生途径的进化树,输出"yes",否则输出"no"。
输入样例:
4
2 spots firebreathing
0
1 flying
2 telepathic flying
输出样例:
yes
这个输入样例与上图所示的合法进化树一致。
供题:Brian Dean
翰林课程体验,退费流程快速投诉邮箱: yuxi@linstitute.net 沪ICP备2023009024号-1