Футбольні парадокси#4882
Після того, як збірна Бразилії з футболу виграла Кубок світу, її перемогла італійська команда. Потім італійці програли болгарам, а болгари, у свою чергу, поступилися Люксембургу. Чи означає це, що Люксембург сильніший за Бразилію?
Подібні парадокси виникають, тому що перемога у матчі не підкоряється властивості транзитивності. Тобто з наведеної ситуації зовсім не випливає, що Люксембург обов’язково виграє у Бразилії. Цей феномен зацікавив Петю, і він вирішив проаналізувати результати всіх відомих йому матчів. Петя хоче знайти найдовшу послідовність ігор з такою властивістю: переможець будь-якої гри цієї послідовності (крім останньої) обов’язково програє у наступній грі. При цьому має зберігатися хронологічний порядок проведення ігор, тобто кожен наступний матч у послідовності повинен був бути зіграний пізніше попереднього. Петю не турбує, чи закінчується послідовність ігор на тій же команді, з якої починалася. Головне для нього — кількість ігор у послідовності.
Вхідний файл містить хронологічно відсортований список ігор, тобто кожна гра відбулась пізніше попередньої. У першому рядку — одне ціле число — кількість зіграних матчів (0 < n \leq 10000). У наступних рядках наведено опис кожної гри. Кожен рядок — це сім символів: перші три символи — ідентифікатор команди-переможця, четвертий символ — дефіс, п’ятий–сьомий символи — ідентифікатор команди, що програла. Кожен ідентифікатор команди являє собою рівно три великі латинські літери. Загальна кількість різних ідентифікаторів команд у вхідному файлі не перевищує .
У першому рядку виведіть максимальну кількість матчів у шуканій послідовності. В другому рядку виведіть послідовність команд, починаючи з тієї, яка виграла останній матч послідовності, і закінчуючи тією, яка програла перший матч. Якщо існує декілька варіантів найдовших послідовностей, дозволяється вивести будь-який з них.
Приклад 1