129. Родословная: подсчет уровней

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

Программа получает на вход число элементов в генеалогическом древе $N$. Далее следует $N-1$ строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имяпотомка имяродителя.

Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.

Эта задача имеет решение сложности $O(n)$, но вам достаточно написать решение сложности $O(n^2)$ (не считая сложности обращения к элементам словаря). Пример ниже соответствует приведенному древу рода Романовых.