|
Фруктовый сок
(Время: 1 сек. Память: 32 Мб Сложность: 66%)
Женя недавно купил себе новую соковыжималку. Теперь по утрам он и его братья и сестры пьют свежевыжатый фруктовый сок. А это, между прочим, очень полезно! Недавно они поняли, что можно пить сок, выжатый не только из одного вида фруктов, как, например, апельсиновый, но и различные смеси, например, виноградно-яблочный.
В Жениной семье все очень любят сок, поэтому могут утром выпить не один стакан, причем разных видов сока. Например, его сестра Катя очень любит грейпфрутовый и апельсиновый соки. Женя, как наиболее технически грамотный человек, каждое утро занимается приготовлением соков.
Опишем подробнее, как работает соковыжималка. В нее загружаются фрукты, они проходят отжим в центрифуге, обезвоженная мякоть сбрасывается в отдельный резервуар, а сок попадает в специальную емкость.
Основная проблема состоит в том, что эту емкость иногда приходится мыть. Например, если после приготовления апельсинового сока, необходимо приготовить яблочный, то емкость надо мыть, иначе получится апельсиново-яблочный сок. Более формально, пусть сок A состоит из компонентов a1, ... , an, а сок B - из компонентов b1, ... , bm. Сок B можно готовить после сока A, если любой из компонентов сока A является компонентом сока B. В противном случае емкость для сока надо помыть.
Женя не очень любит мыть посуду, поэтому хочет мыть емкость как можно меньшее число раз. Помогите ему.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество различных соков, которые требуется приготовить (N ≤ 300). Каждая из последующих N строк описывает один из соков. Описание сока состоит из числа k его компонентов (1 ≤ k ≤ 300) и списка этих компонентов. Каждый из компонентов сока описывается словом длиной до 30 символов из строчных и прописных букв английского алфавита. Прописные и строчные буквы различаются. Различные компоненты имеют различные названия.
Выходные данные
В выходной файл OUTPUT.TXT выведите минимальное количество раз, которое Жене придется помыть емкость для сока. Учитывайте при этом, что емкость для сока надо помыть и после приготовления последней порции сока.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
1 Apple
2 Apple Orange
1 Orange
2 Orange Pineapple | 2 |
| 2 | 3
1 Apple
1 Orange
1 Mango | 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
