Дано дерево T состоящее из n вершин (пронумерованных целыми числами от 1 до n). В каждой вершине записана некоторая буква. Корень дерева расположен в вершине 1.
Рассмотрим поддерево дерево Tv некоторой вершины v. Вдоль любого просто пути, начинающегося в v и заканчивающегося в некоторой вершине 
(возможно, в самой v), можно прочитать некоторую строку. Обозначим количество различных строк, которые можно прочитать таким способом как 
.
Дополнительно: для каждой вершины v дано целое число cv. Нас интересуют вершины, в которых значение 
как можно больше.
Вы должны вычислить две величины — максимальное значение и количество вершин v с максимальным .
Выходные данные
Выведите два числа — значение 
для всех 1 ≤ i ≤ n и количество вершин v, для которых 
.
Примечание
В первом примере дерево выглядит следующим образом:
Наборы строк, которые могут быть прочитаны из вершин:
Наконец, значения 
таковы:
Во втором примере значения 
таковы: (5, 4, 2, 1, 1, 1).Различные строки, которые можно прочитать из вершины 2 таковы: 
; обратите внимание, что 
может быть прочитано как на пути до вершины 3, так и на пути до вершины 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1 2 7 20 20 30 40 50 50 50
cacabbcddd
1 2
6 8
7 2
6 2
5 4
5 9
3 10
2 5
2 3
|
51
3
|
|
2
|
6
0 2 4 1 1 1
raaaba
1 2
2 3
2 4
2 5
3 6
|
6
2
|