Задача №114105. Родословная: подсчет уровней
В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель.
Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна \(0\), у любого другого элемента высота на \(1\) больше, чем у его родителя.
Вам дано генеалогическое древо, определите высоту всех его элементов.
Программа получает на вход число элементов в генеалогическом древе \(n\ (n \le 10^5)\).
Далее следует \(n−1\) строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид "имя_потомка имя_родителя" (без кавычек).
Суммарная длина всех строк в тесте не превосходит \(2\cdot10^6\)
Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.
9 Alexei Peter_I Anna Peter_I Elizabeth Peter_I Peter_II Alexei Peter_III Anna Paul_I Peter_III Alexander_I Paul_I Nicholaus_I Paul_I
Alexander_I 4 Alexei 1 Anna 1 Elizabeth 1 Nicholaus_I 4 Paul_I 3 Peter_I 0 Peter_II 2 Peter_III 2