Генеалогическое древо — это графическая схема, описывающая родственные связи в пределах одной семьи. Начало такого дерева — это один предок (родоначальник) или супруги и далее цепочка строится вниз. По заданному генеалогическому древу, определите у каждого элемента число его потомков (не считая самого элемента).
Входные данные
Программа получает на вход число элементов в генеалогическом древе
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 0
Alexei 1
Anna 4
Elizabeth 0
Nicholaus_I 0
Paul_I 2
Peter_I 8
Peter_II 0
Peter_III 3
|