Codeforces Round 603 (Div. 2) |
---|
Закончено |
Один малоизвестный хакер захотел заполучить пароль администратора от тестирующей системы AtForces, чтобы узнать задачи с предстоящего контеста. Чтобы достичь этого, он пробрался в кабинет администратора и украл листочек, на котором записан список из $$$n$$$ паролей — строк, состоящих из строчных букв латинского алфавита.
Хакер вернулся домой и начал готовиться ко взлому. Он обнаружил, что в системе содержатся только пароли с украденного листочка, и что система определяет эквивалентность паролей $$$a$$$ и $$$b$$$ следующим образом:
Если в системе установлен некоторый пароль, а применяется ему эквивалентный, то пользователь получает доступ к системе.
К примеру, если в списке содержатся пароли «a», «b», «ab», «d», то с точки зрения системы пароли «a», «b», «ab» эквивалентны друг другу, а пароль «d» никакому другому не эквивалентен. Иначе говоря, если:
Известно, что ровно один пароль из списка является паролем администратора от тестирующей системы. Помогите хакеру понять, какое минимальное количество паролей понадобится использовать при взломе, чтобы гарантированно получить доступ к системе. Имейте в виду, что хакер не знает, какой именно пароль установлен в системе.
В первой строке задано число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество паролей. В следующих $$$n$$$ строках заданы пароли администратора из списка — непустые строки $$$s_i$$$, длины которых не превышают $$$50$$$ символов. Некоторые строки могут совпадать.
Гарантируется, что суммарная длина всех паролей не превышает $$$10^6$$$ символов. Все они состоят только из строчных букв латинского алфавита.
В единственной строке выведите минимальное количество паролей, использование которых позволит гарантированно получить доступ к системе.
4 a b ab d
2
3 ab bc abc
1
1 codeforces
1
Во втором примере необходимо использовать любой из паролей, чтобы получить доступ к системе.
Название |
---|