Vocabulary Quiz

Bessie is helping Elsie prepare for her upcoming vocabulary quiz. The quiz words are selected from a word library consisting of M distinct words, with the property that no word is a prefix of another. When the library is non‐empty, Bessie chooses a word from the library, removes it, and reads its characters one by one from left to right. Elsie must tell Bessie as soon as she can uniquely determine the word. Bessie has predetermined the order of the words \(w_1, w_2, \dots, w_M\). If Elsie answers as fast as possible, how many characters will Bessie read for each word?

The words are given in a compressed format. First, we define \(N+1\) (\(1 \le N \le 10^6\)) distinct words as follows:

• The 0th word is the empty string.
• For each \(1 \le i \le N\), the \(i\)th word is obtained by appending an extra character to the \(p_i\)th word (with \(0 \le p_i < i\)). The extra character is chosen such that all \(N+1\) words are distinct.

The word library consists of all those \(N+1\) words that are not a prefix of any other word. The quiz order \(w_1, w_2, \dots, w_M\) is defined by the order in which these leaf words appear (i.e. in increasing order of their index). For each quiz word \(w\), when Bessie reads it, Elsie can stop as soon as she hears a prefix of length \(k\) for which there is exactly one word in the current library (i.e. among the words that have not yet been quizzed). Determine, for each word in the quiz order, the number of characters that Bessie will read assuming Elsie answers optimally.

Note on Uniqueness: For any word \(w\), let \(w[1 \dots k]\) denote its prefix of length \(k\). When the current library has several words sharing that prefix, Elsie cannot yet identify \(w\). As soon as the count becomes exactly one, she knows the word Bessie is pronouncing.

Input Format: The first line contains a single integer \(N\). Each of the next \(N\) lines contains an integer \(p_i\) and a character (separated by space), representing that the \(i\)th word is obtained by appending that character to the \(p_i\)th word.

Output Format: Let \(M\) be the number of leaf words (i.e. words in the library). Output \(M\) lines, where the \(j\)th line contains a single integer indicating the number of characters Bessie reads when quizzing the \(j\)th word in the predetermined order.

inputFormat

The first line contains an integer \(N\) (number of word constructions). Each of the next \(N\) lines contains an integer \(p_i\) (with \(0 \le p_i < i\)) and a character, separated by a space. All characters appended are such that the resulting \(N+1\) words are distinct. The word library is defined as all words that are not a prefix of any other word.

outputFormat

Output \(M\) lines, where each line contains a single integer: the number of characters read by Bessie to uniquely identify each quiz word, in the order \(w_1, w_2, \dots, w_M\).

sample

3
0 a
0 b
0 c

1
1
1