EduBrick

G. Фруктовый сок

2000 мс · 256 МБ · всё или ничего

Соковыжималка готовит соки один за другим. Сок BB можно готовить сразу после сока AA, если каждый компонент сока AA входит и в сок BB; иначе ёмкость надо помыть. Мыть надо и после последнего сока.

Нужно приготовить все NN соков в каком-нибудь порядке так, чтобы мыть пришлось как можно меньше раз.

Формат ввода

В первой строке NN (1≤N≤3001 \le N \le 300) — количество соков. В каждой из следующих NN строк описан один сок: сначала число компонентов kk (1≤k≤3001 \le k \le 300), затем kk названий компонентов.

Название состоит не более чем из 3030 строчных и прописных латинских букв; прописные и строчные различаются. Различные компоненты имеют различные названия, соки попарно различны.

Формат вывода

Выведите минимальное количество раз, которое придётся помыть ёмкость.

Примеры

ввод
4
1 Apple
2 Apple Orange
1 Orange
2 Orange Pineapple
вывод
2
ввод
3
1 Apple
1 Orange
1 Mango
вывод
3
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.