Задача P. Перепутанные диски ≡

Автор:Рекомендации   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Например, пусть у Васи есть три компакт-диска с играми — "Цивилизация", "Тетрис" и "Сапер". Пусть Вася сначала начал играть в "Цивилизацию", а затем решил поиграть в "Тетрис". Тогда после этого диск с "Цивилизацией" окажется в коробке от "Тетриса". Пусть затем он решил поиграть в "Сапера". Тогда диск от "Тетриса" окажется в коробке от "Сапера". Если после этого он снова решит поиграть в "Цивилизацию" (заметим, что для этого он достанет ее из коробки от "Тетриса"), то игра "Сапер" окажется в коробке от "Тетриса", а "Цивилизация" — в CD-приводе Васиного компьютера.

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

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

Первая строка входного файла содержит число n — количество игр, в которые играл Вася, при этом Вася мог играть в одну и ту же игру несколько раз. Следующие n строк содержат названия игр в том порядке, в котором играл Вася. Все названия состоят из латинских букв, цифр и пробелов.

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

Выведите в выходной файл k строк, где k — количество различных игр, в которые играл Вася. Каждая строка должна иметь вид "game - box", где game — название игры, а box - название игры, в коробке от которой лежит игра game. Если соответствующая игра лежит в CD-приводе компьютера, вместо box выведите "*" (звездочку). Выводите игры в произвольном порядке.

Ограничения

1 ≤ n ≤ 1000, длина названия не превышает 50 символов.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4
Civilization
Tetris
Minesweeper
Civilization
 
Civilization - *
Tetris - Minesweeper
Minesweeper - Tetris
0.033s 0.007s 15