Задача 78. На Парнас! ≡

Условие

Здесь продают билеты на Парнас,

Здесь нервничает очередь у касс:

 — Последний кто? Молчат, последних нету...

Фронтовики, толкучка не про нас,

Локтями грех орудовать поэту!

...

Юлия Друнина, "Здесь продают билеты на Парнас", 1964 г.

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

Формат входных данных

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

Формат выходных данных

Выведите одно слово — имя поэта, стоящего последним в самой короткой очереди. Если подходящих ответов несколько — выведите лексикографически наименьшее.

Ограничения

1 ≤ n ≤ 10⁵

Длина имени любого поэта не превышает 10.

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере восемь поэтов составили две очереди в кассы (смотри схему). В одной из них пять человек, в другой — всего три. Юле выгоднее занять очередь за Маяковским.

Во втором примере две очереди равной длины. Из двух имён (a и d) выбираем лексикографически наименьшее.

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

8
Pushkin Chukovsky
Lermontov Yesenin
Nekrasov Pushkin
Chukovsky Cashbox
Mayakovsky Lermontov
Svetlov Nekrasov
Tsvetayeva Svetlov
Yesenin Cashbox

Mayakovsky

4
a b
b Cashbox
c Cashbox
d c

a