Cow Evolution

题目描述

现在是 3019 年，过去的一千年里牛发生了令人惊讶的进化，产生了具有各种有趣特征的牛。

牛的进化记录可以用一棵树来描述：从根节点的一头基础祖先牛开始，它没有任何特殊特征。在树的每一层后代中，要么所有牛都进化出一种新特征（例如下面的喷火能力，其中所有有斑点的牛最终都学会了喷火），要么牛群发生分化：一部分牛进化出一种新特征（例如飞行），另一部分则没有。

树底部的叶子表示 3019 年所有最终形成的子种群。没有任何两个叶子（子种群）拥有完全相同的一组特征。例如，子种群 #1 的牛没有任何特殊特征，而子种群 #3 的牛是会心灵感应的飞行牛。相比之下，子种群 #2 的牛会飞但不会心灵感应。子种群 #3 在“飞行 + 心灵感应”的组合上是独一无二的。

如果每一种新进化出来的特征都恰好起源于树上的一条边（即它只在历史中的某一个时刻出现一次），则称这样的进化树是“proper”的。例如，如果“斑点”在两条不同的分支上分别进化出来，那么这棵树就不是 proper 的。给定 3019 年这些子种群的描述，请判断它们是否能由一棵 proper 的进化树来描述。

输入格式

第一行输入为子种群数量 $N$（$2 \leq N \leq 25$）。接下来 $N$ 行每行描述一个子种群。

每行以一个整数 $K$ 开始（$0 \leq K \leq 25$），随后给出该子种群中所有牛具备的 $K$ 个特征。特征为长度不超过 20 的小写字母字符串（a..z）。任意两个子种群的特征集合都不完全相同。

输出格式

如果可以构造一棵 proper 的进化树来解释这些子种群的起源，输出 "yes"；否则输出 "no"。

4
2 spots firebreathing
0
1 flying
2 telepathic flying

yes

提示

该样例输入对应于上图所示的 proper 进化树。 题目来源：Brian Dean

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze