Футбольные парадоксы
После того, как сборная Бразилии стала Чемпионом Мира по футболу, она проиграла сборной Италии, которая, в свою очередь, проиграла сборной Болгарии, а та - сборной Люксембурга. Так что же, получается, что Люксембург сильнее Бразилии?
Такие парадоксы происходят довольно часто, и удивляться этому не стоит, так как победа в матче не обладает свойством транзитивности, то есть описанное выше не означает, что при встрече сборных Бразилии и Люксембурга обязательно выиграет Люксембург. Это заинтересовало Петю, и он решил проанализировать результаты всех матчей, которые он знает, и выбрать из них самую длинную цепочку игр, обладающую следующим свойством - победитель любого матча этой цепочки (кроме последнего) должен проиграть в следующем матче этой цепочки. Заметьте, что хронологический порядок игр должен сохраниться, то есть следующий матч в цепочке должен быть сыгран позже предыдущего. Пете не важно, заканчивается ли цепочка игр той же командой, с которой начинается, или нет. Прежде всего, его волнует количество игр в ней.
Входные данные
Во входном файле содержится отсортированная хронологически последовательность игр, то есть каждая следующая игра в этой последовательности была сыграна позже предыдущей. В первой строке входного файла записано целое число n - количество сыгранных игр (0 < n ≤ 10000). В каждой из следующих n строк содержится описание одной игры. Каждая игра описывается строкой из семи символов. Первые три символа - идентификатор выигравшей команды, четвертый символ - тире, символы с пятого по седьмой - идентификатор проигравшей команды. Идентификатор команды всегда является трехбуквенным и состоит только из заглавных латинских букв. Количество различных идентификаторов команд во входном файле не превышает 200.
Выходные данные
В первую строку выходного файла выведите максимальное количество матчей в искомой цепочке. Во вторую строку выведите цепочку команд, начиная с команды, победившей в последнем матче цепочки, и заканчивая командой, проигравшей в первом. Если вариантов наиболее длинных цепочек несколько, выведите любой из них.