Задача №3774. Родословная: число потомков

Для каждого элемента дерева определите число всех его потомков (не считая его самого).

Входные данные

Формат входных данных совпадает с задачей W.

Выходные данные

Формат выходных данных совпадает с задачей W. Выведите список всех элементов в лексикографическом порядке, для каждого элемента выводите количество всех его потомков.

Примечание

Решение должно иметь сложность \(O(N)\), не считая сложности обращения к элементам словаря и сортировки результата.

Примеры
Входные данные
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
Сдать: для сдачи задач необходимо войти в систему