Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Графы

(Время: 2 сек. Память: 16 Мб Сложность: 70%)

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12
AAABBB
BBBCCC
1
22
AAABBB
CCCDDD
2
33
AAABAA
ABAAAB
AABBAA
2

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

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ