# ДОП.)  В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.
# Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота
# равна 0, у любого другого элемента высота на 1 больше, чем у его родителя.
# Вам дано генеалогическое древо, определите высоту всех его элементов.
# Программа получает на вход число элементов в генеалогическом древе N. Далее следует N−1 строка, задающие родителя
# для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.
# Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого
# элемента необходимо вывести его высоту.
# Примечание
# Эта задача имеет решение сложности O(n), но вам достаточно написать решение сложности O(n2) (не считая сложности
# обращения к элементам словаря).

# Рекурсивная функция определения высоты определённого имени компонента в дереве
def CalculateHeight(component):
    if component in Tree: # Если компонент есть в дереве, то идём глубже
        return 1 + CalculateHeight(Tree[component])  # Делаем инкремент высоты на единицу
    else:
        return 0

Tree = {}  # Словарь, содержащий в себе элементы дерева типа: (имя, высота)
print("Enter the number of elements in the tree:")
N = int(input())
for i in range(N - 1):
    print("Now enter information about", (i + 1), "/", (N - 1), "descendant and his parent:")
    desc, parent = input().split()  # Получаем на вход имя потомка и имя его родителя
    Tree[desc] = parent  # Записываем в словарь
Heights = {}  # Словарь, содержащий в себе высоты элементов дерева
names_and_values = set(Tree.keys()).union(set(Tree.values()))  # Множество имён в объединении с множеством высот
for component in names_and_values:  # Для каждой компоненты из такого множества...
    Heights[component] = CalculateHeight(component)  # Рекурсивно для каждого имени считаем высоту
Heights = sorted(Heights.items())  # Сортировка
for name, value in Heights:
    print(name, value)  # Печатаем поэлементно его имя и высоту в дереве