Генеалогическое древо — это графическая схема, описывающая родственные связи в пределах одной семьи. Начало такого дерева — это один предок (родоначальник) или супруги и далее цепочка строится вниз. Сопоставим с каждым элементов дерева целое неотрицательное число, называемое высотой. У самого верхнего предка высота 0, у каждого следующего потомка высота на 1 больше, чем у его родителя.
По заданному генеалогическому древу, определите высоту всех его элементов.
Входные данные
Программа получает на вход число элементов в генеалогическом древе
N. Далее следует
N−1 строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид
имя_потомка имя_родителя.
Выходные данные
Программа должна вывести список всех элементов древа в лексикографическом порядке. После вывода имени каждого элемента необходимо вывести его высоту.
Пример
| № |
Входные данные |
Выходные данные |
| 1 |
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
|