eolymp
bolt
Try our new interface for solving problems
Məsələlər

Эволюция коров

Эволюция коров

Сейчас 3019 год, и за последнюю тысячу лет произошло удивительная эволюция крупного рогатого скота, в результате чего появились коровы со всевозможными интересными особенностями. История эволюции крупного рогатого скота может быть описана как дерево, начинающееся с основной предковой коровы в корне без каких-либо особых особенностей. На каждом последующем уровне в дереве либо все коровы развивают новую особенность (например, огнедышание, а ниже, например, все коровы с пятнами дышат огнем), либо происходит разделение в популяции, где некоторые коровы развивают новую функцию (например, полет), а некоторые нет. \includegraphics{https://static.e-olymp.com/content/f9/f937f3138ecdc90a2fcad67d972fc189e16027f2.gif} Листья в нижней части дерева указывают на все полученные субпопуляции коров в 3019 году. Ни один лист (субпопуляции) не содержит идентичных наборов признаков. Например, подгруппа #_1 содержит коров без особенностей, а подгруппа #_3 содержит телепатических летающих коров. В субпопуляции #_2, напротив, есть летающие коровы, которые не обладают телепатическими способностями. Подгруппа #_3 уникальна тем, что сочетает летающих и телепатических коров. Эволюционное дерево, подобное приведенному выше, называется "правильным", если каждая вновь возникающая особенность берет свое начало ровно на одном ребре дерева (например, оно эволюционировало в определенный момент истории). Например, дерево было бы неподходящим, если бы пятна превратились в две отдельные ветви. По заданному описанию субпопуляций коров в 3019 году, определите, можно ли их описать соответствующим деревом эволюции. \InputFile Первая строка содержит количество субпопуляций $n~(2 \le n \le 25)$. Каждая из следующих $n$ строк описывает подгруппу популяции. Строка начинается с целого числа $k~(0 \le k \le 25)$, затем следуют $k$ характеристик всех коров в этой подгруппе. Характеристики --- это строки, содержащие до $20$ строчных символов $(a .. z)$. Не существует двух подгрупп популяций с одинаковыми характеристиками. \OutputFile Выведите "\textbf{yes}", если возможно сформировать правильное эволюционное древо, объясняющее происхождение этих субпопуляций, и "\textbf{no}" в противном случае.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4
2 spots firebreathing
0
1 flying
2 telepathic flying
Çıxış verilənləri #1
yes
Mənbə 2019 USACO US Open, Бронза