ТПУ: основной тур
I. Маркерная доска
У Ильи есть листок со списком из n слов одинаковой длины (очень похоже на то, что он зачем-то взял его у Виктора).
Он придумал себе такое развлечение: часть слов он сразу же записывает на маркерной доске, а далее дописывает одно слово из оставшихся за другим так, чтобы каждое новое слово отличалось от какого-либо ранее выписанного ровно одной буквой.
Например, если слово «CAT
» уже написано на доске, то Илья может написать на ней слова «CAR
» и «BAT
», что, в свою очередь, откроет ему путь к написанию новых слов.
Какое минимальное количество слов ему нужно изначально написать на доске, чтобы впоследствии он смог написать на доске все слова из своего списка?
В первой строке входных данных содержится одно целое положительное число n, не превосходящее 100 — количество слов в списке Ильи.
В последующих n строках содержатся сами слова. Все слова имеют одинаковую ненулевую длину, не превосходящую 1000, и состоят только из прописных букв латинского алфавита.
Требуется вывести единственное целое число — минимальное количество слов, которые Илье изначально придётся выписать на доску.
Стандартный ввод | Стандартный вывод |
---|---|
5 FOO BAR BAZ ZOO ZOD | 2 |