Дано дерево из \(n\) вершин. На каждой вершине записано число; на вершине \(i\) записано число \(a_i\).
Предположим, мы подвесили дерево за вершину \(v\) (сделали эту вершину корнем). Назовем \(v\) различающим корнем, если выполняется следующее условие: в каждом пути из \(v\) до некоторого листа дерева все значения, записанные на вершинах, различны. Значения, встречающихся на различных путях, могут совпадать, но значения на каждом пути, рассматриваемом в отдельности, должны быть различны.
Посчитайте количество различающих корней заданного дерева.
Выходные данные
Выведите одно целое число — количество различающих корней в дереве.
Примечание
В первом примере из условия вершины \(1\), \(2\) и \(5\) — различающие корни.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 5 1 1 4
1 2
1 3
2 4
2 5
|
3
|
|
2
|
5
2 1 1 1 4
1 2
1 3
2 4
2 5
|
0
|