#1202

Операции

Темы: [Конечные автоматы] [НОД и алгоритм Евклида]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2006, 2 тур, Задача A ]

#1203

Кенгуренок Лео

Темы: [Обход в ширину] [Способы задания графа]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2006, 2 тур, Задача B ]

#1204

Студенческие годы Пекки

Темы: [Сортировка записей] [Быстрая сортировка]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2006, 2 тур, Задача C ]

Пекка вырос, стал студентом, и подрабатывает в свободное от учебы время на разгрузке желез- нодорожных вагонов. Ему требуется погрузить товары из одного состава в другой, стоящий рядом на параллельном пути.

Известно, какой товар находится в каждом из вагонов первого состава, и какой товар должен быть в каждом из вагонов второго состава. Товар из любого вагона первого состава легко пере- грузить в стоящий напротив вагон второго состава с помощью транспортера. Проблема в том, что порядок вагонов первого состава может не соответствовать порядку вагонов второго состава.

Чтобы правильно поместить груз из одного вагона первого состава в вагон второго состава, Пекка может сдвигать (но только вперед — под горку) какой-либо из составов на длину одного вагона, выпив для этого баночку энергетического напитка.

Пекка очень заботится о своем здоровье и не хочет злоупотреблять энергетической жидкостью. Помогите Пекке определить, какое минимальное количество баночек напитка ему потребуется вы- пить для того, чтобы перегрузить все товары из первого состава.

Считается, что:

Все вагоны одинаковой длины.
Каждому типу товара соответствует определенное слово — его название (“Oil”, “Wood” и т. д.)
Количество разгружаемых вагонов первого состава с товарами любого типа совпадает с количеством загружаемых вагонов второго состава для товаров такого же типа.
Может быть несколько вагонов первого состава с одинаковым типом товара. При этом любой из них можно перегружать в соответствующие вагоны второго состава (но только полностью).
Если вагон первого состава с определенным типом товара встал рядом с вагоном второго состава, предназначенного для данного типа груза, то Пекка может как осуществить перегрузку, так и отказаться от нее
Изначально составы стоят таким образом, что первый вагон первого состава стоит рядом с первым вагоном второго состава, а последний вагон первого состава — рядом с последним вагоном второго состава.

Формат входного файла

В первой строке входного файла записано количество вагонов в составах N (1 ≤ N ≤ 100 000). Далее следуют N строк, описывающих вагоны первого состава в порядке, в котором они соединены в состав. В каждой строке записано название груза, находящегося в соответствующем вагоне. Название содержит от одной до десяти больших и маленьких букв латинского алфавита. Названия считаются одинаковыми, если они совпадают с учетом регистра (например, “Oil” и “oil” — разные грузы). Затем записаны N строк, аналогичным образом описывающих вагоны второго состава.

Формат выходного файла

Выведите минимальное количество баночек энергетического напитка, которые потребуются Пекке для того, чтобы осуществить погрузку..

Группы тестов:

Группа 0 : Тест из условия (тест 1). 0 баллов.
Группа 1 : N ≤ 10 (тесты 2-6). 30 баллов.
Группа 2 : Ответ на задачу не превосходит 100 (тесты 7-11). 30 баллов.
Группа 3 : Дополнительных ограничений нет (тесты 12-50). 40 баллов.

Баллы за группу тестов выставляются только при корректной работе программы на всех тестах группы.

Примеры

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

3
Oil
Wood
Grain
Wood
Grain
Oil

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