Графы

Однажды в древнее государство Оссия приехал ученый японец Хисикоши. Он обнаружил, что в этом государстве есть одна большая проблема – дороги, а точнее их отсутствие. Еще он обнаружил другую проблему – графов (а было их N), которые, мягко говоря, не отличались особенным уровнем интеллекта. Хисикоши решил помочь построить дороги. С рабочей силой проблем не было, поэтому он решил подойти к этому мероприятию с выдумкой. Он узнал имена всех графов и записал их по-японски (а в Японии, как известно, пользуются иероглифами). Он решил, что надо провести дорогу между замками двух графов (и ввести на ней одностороннее движение от первого ко второму – чтобы интереснее было), если последняя буква имени первого графа совпадает с первой буквой имени второго. Однако, оказалось, что не от каждого графа можно доехать до всех других. Тогда он решил поселить еще несколько графов и дать им имена так, чтобы теперь можно было бы доехать от любого графа до любого другого. Какое наименьшее количество графов ему надо добавить?

Будем считать, что японский иероглиф однозначно кодируется тремя английскими буквами. И каждой трехбуквенной комбинации соответствует свой иероглиф.

Входные данные

В первой строке входного файла INPUT.TXT находится целое число N – количество графов (1 ≤ N ≤ 100 000). В следующих N строках написаны их имена. При этом гарантируется, что длина каждого имени (в английских символах) делится на 3. Имена написаны большими английскими буквами. Каждое имя содержит от одного до десяти иероглифов.

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное целое число – минимальное количество графов, которые должен поселить Хисикоши.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]