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