28816번 - Игра с деревом 다국어

문제

Путешествуя по вселенной игр, Ральф и Ванилопа обнаружили удивительную игру. В этой игре необходимо очень быстро считать, что очень им понравилось. Действие игры происходит вокруг волшебной яблони.

Изначально яблоня состоит только из одного яблока --- корня. Номер этого яблока равен 1. После этого Ральф добавляет новое яблоко, которое он связывает с уже существующим, с помощью ветки. На каждой ветке Ральф записывает букву латинского алфавита от $a$ до $z$.

Ванилопа в свою очередь иногда срывает некоторое яблоко. Вместе с яблоком исчезает и ветка, с помощью которой оно было связано. Гарантируется, что никакое другое яблоко не подвешено к яблоку, которое удалит Ванилопа.

Назовем словом последовательность букв на ветках, идущих от корня к яблоку. Подсловом назовем непустое количество подряд идущих букв в слове.

Вам необходимо после каждого действия посчитать количество различных подслов. Подслова считаются различными, если существуют позиции, в которых стоят различные буквы.

입력

В первой строке содержатся два целых числа $q$ --- количество действий (1ドル \leq q \leq 100,000円$). Каждая из последующих $q$ строк содержит описание действий в следующем формате: 1ドル$ $p$ $c$ --- означает, что Ральф добавляет яблоко с минимальным положительным номером, который еще не был использован (1ドル \leq p \leq n$). Предком нового яблока является яблоко $v,ドル а на ветке написана латинская буква $c$. 2ドル$ $v$ --- Ванилопа срывает яблоко с номером $v$. Гарантируется, что корневое яблоко не будет сорвано, а также никакое яблоко не будет сорвано дважды.

출력

После каждого действия выведите количество различных подслов.

제한

노트

После первой операции есть слово <<a>>. Различные подслова: <<a>>.

После второй операции слова <<a>>, <<b>>. Различные подслова: <<a>>, <<b>>.

После третьей операции слова <<a>>, <<b>>, <<a>>. Различные подслова: <<a>>, <<b>>.

После четвертой операции слова <<a>>, <<b>>, <<ac>>. Различные подслова: <<a>>, <<b>>, <<ac>>, <<c>>.

После пятой операции слова <<a>>, <<ac>>. Различные подслова: <<a>>, <<ac>>, <<c>>.