Problem
Certa vez, Konstantin, tendo participado da próxima, já a 13ª Olimpíada Internacional, voltava de trem para casa. Ele, como sempre, sentou-se e pensou no sentido da vida, resolvendo simultaneamente problemas de programação. Depois de algum tempo, Konstantin cochilou, mas o problema é que, para acordar, ele deve resolver o problema que surgiu em sua cabeça e o assombra!
Desta vez, Konstantin sonhou com uma árvore que inicialmente consistia em apenas um vértice com o número 1. No problema que ele definiu, novos vértices foram adicionados gradualmente à árvore. No i-ésimo segundo, um vértice com o número i+1 foi adicionado à árvore, que foi suspenso como filho do vértice p
i, e na aresta entre os vértices i+1 e p
i a letra c
i foi escrita.
Cada caminho da raiz da árvore até o vértice v corresponde a uma certa string obtida escrevendo os símbolos escritos nas arestas do caminho atual na ordem da raiz até o vértice v. Konstantin enfrentou uma tarefa difícil à primeira vista - após cada adição de um novo vértice, conte o número de strings únicas começando na raiz da árvore (vértice número 1) e terminando em algum outro vértice.
Em seu sonho, Konstantin não é um gênio, então ele mesmo não pode resolver esse problema. Ajude Konstantin a resolver o problema e acordar.
Entrada:
A primeira linha contém o número n - o número de solicitações para adicionar um novo nó à árvore (1 <= n <= 300000).
As próximas n linhas descrevem solicitações para adicionar vértices. A i-ésima consulta é descrita pelos parâmetros p
i (1 <= p
i <= i) ec
i, que significa que o vértice adicionado com o número i+1 é suspenso do vértice com o número p
i como filho, e o símbolo c
i é escrito na aresta resultante - uma letra minúscula do alfabeto latino.
Saída:
Imprima n linhas. Na i-ésima linha imprima a resposta para o problema de Konstantin após adicionar o i+1-ésimo vértice.
Exemplos:
| Entrada |
Saída |
2
1b
2p |
1
2 |
3
1º
1º
2 j |
1
1
2 |