Arpa has a rooted tree (connected acyclic graph) consisting of $n$ vertices. The vertices are numbered $1$ through $n$, 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·10^5)$ − the number of vertices in the tree.

$(n-1)$ lines follow, the $i$-th of them contain an integer $p_{i+1}$ and a letter $c_{i+1}\ (1≤p_{i+1}≤i,\ c_{i+1}$ is lowercase English letter, between $a$ and $v$, inclusively), that mean that there is an edge between nodes $p_{i+1}$ and $i+1$ and there is a letter $c_{i+1}$ 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.