_Just in case somebody missed it: we have wonderful girls in Arpa’s land._
Arpa has a rooted tree (connected acyclic graph) consisting of n vertices. The vertex 1 is the root. There is a letter written on each edge of this tree. Mehrdad is a fan of _Dokhtar-kosh_ things. He call a string Dokhtar-kosh, if we can shuffle the characters in string such that it becomes palindrome.
He asks Arpa, for each vertex v, what is the length of the longest simple path in subtree of v that form a Dokhtar-kosh string.
The first line contains integer n (1 ≤ n ≤ 5·105) — the number of vertices in the tree.
(n - 1) lines follow, the i-th of them contain an integer pi and a letter ci (1 ≤ pi < i, ci is lowercase English letter), that mean that there is an edge between nodes pi and i and there is a letter ci written on this edge.
Print n integers. The i-th of them should be the length of the longest simple path in subtree of the i-th vertex that form a Dokhtar-kosh string.
## Input
The first line contains integer n (1 ≤ n ≤ 5·105) — the number of vertices in the tree.(n - 1) lines follow, the i-th of them contain an integer pi and a letter ci (1 ≤ pi < i, ci is lowercase English letter), that mean that there is an edge between nodes pi and i and there is a letter ci written on this edge.
## Output
Print n integers. The i-th of them should be the length of the longest simple path in subtree of the i-th vertex that form a Dokhtar-kosh string.
[samples]
**Definitions**
Let $ T = (V, E) $ be a rooted tree with $ n $ vertices, where $ V = \{1, 2, \dots, n\} $ and vertex $ 1 $ is the root.
Each edge $ (p_i, i) $ for $ i = 2, \dots, n $ is labeled with a character $ c_i \in \Sigma $, where $ \Sigma $ is the set of lowercase English letters.
For any path $ P $ in $ T $, let $ s(P) $ denote the string formed by concatenating the edge labels along $ P $.
A string $ s $ is *Dokhtar-kosh* if it can be rearranged into a palindrome, i.e., at most one character has odd frequency.
For each vertex $ v \in V $, let $ T_v $ denote the subtree rooted at $ v $.
**Constraints**
1. $ 1 \le n \le 5 \cdot 10^5 $
2. For each $ i \in \{2, \dots, n\} $: $ 1 \le p_i < i $, $ c_i \in \{a, b, \dots, z\} $
**Objective**
For each vertex $ v \in \{1, \dots, n\} $, compute:
$$
f(v) = \max \{ |P| \mid P \text{ is a simple path in } T_v \text{ and } s(P) \text{ is Dokhtar-kosh} \}
$$
Output $ f(1), f(2), \dots, f(n) $.