Тимур любит изучать сложные структуры данных. Ерулан любит изучать простые структуры данных. Тимур зачем-то недавно рассказал про структуру данных «бор» Ерулану: «бор — это корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с сыновьями, помечены разными символами.»
Ерулан решил, что определение слишком сложное и надо бы его сократить. Полученную структуру он назвал «недобор». А именно, «недобор» — это корневое дерево, каждое ребро которого помечено каким-то символом.
Вершины дерева пронумерованы целыми числами от 1 до N, при этом 1 является корнем дерева. Как же найти в «недоборе» количество различных слов, которые можно получить, двигаясь по ребрам от корня?
На первой строке целое число $$$N$$$ от 1 до $$$10^5$$$. Далее (N-1) строка. На $$$i$$$-й строке указан $$$p_i$$$ — родитель $$$i$$$-й вершины и буква, соответствующая ребру между вершинами $$$p_i$$$ и $$$i$$$.
Одно целое число — количество различных слов.
8 1 a 5 d 5 b 1 a 2 b 6 c 4 e
5
В примере даны слова: a, ab, ad, abc, abe.
