Time Limit: 3 seconds

Memory Limit: 256 megabytes

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 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.

提交代码