Bessie и Эльза любя также играть в игру "угадай животное".
Сначала Беси задумывает некоторое животное. Затем Эльза
задаёт серию вопросов, чтобы угадать, какое животное задумала
Беси. На каждый вопрос Беси отвечает "Да" или "Нет".
Например:
Эльза: "Животное летает?"
Беси: "Нет"
Эльза: "Ест траву"
Беси: "Да"
Эльза: "Даёт молоко?"
Беси: "Да"
Эльза: "Делает му-у?"
Беси: "Да"
Эльза: "Корова."
Беси: "Точно!"
Назовём "правдоподобным множеством" множество всех всех животных,
с характеристиками подходящими вопросам Эльзы. Эльза задаёт вопросы
пока в "правдоподобном множестве" останется только одно животное,
после чего она называет его в качестве ответа. Для каждого вопроса
Эльза выбирает характеристику некоторого животного и спрашивает о ней
(даже если ответ не сузит "правдоподобное множество"). Она никогда
не спрашивает об одной и той же характеристике дважды.
Вам даны все животные, которых знают Беси и Эльза и их характеристики.
Определите максимальное количество ответов "Да", которые может получить
Эльза, прежде чем она узнает задуманное животное.
ФОРМАТ ВВОДА (файл guess.in):
Первая строка ввода содержит количество животных, \(N\)
(\(2 \leq N \leq 100\)). Каждая из последующих \(N\) строк описывает
животное. Строка начинается с названия животного, затем идёт целое число
\(K\) (\(1 \leq K \leq 100\)), и затем \(K\) характеристик этого животного.
Названия и характеристики животных это строки из маленьких латинских букв
(a..z), длиной не более 20 символов. Никакие два животных не имеют
полностью совпадающие характеристики.
ФОРМАТ ВЫВОДА (файл guess.out):
Выведите максимальное количество ответов "Да", которые Эльза может получить
прежде чем игра закончится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
bird 2 flies eatsworms
cow 4 eatsgrass isawesome makesmilk goesmoo
sheep 1 eatsgrass
goat 2 makesmilk eatsgrass
|
3
|