题目描述

Arpa 有一棵包含 $n$ 个顶点（编号 $1$ 至 $n$）的有根树（连通无环图），其中顶点 $1$ 为根节点。树的每条边上写有一个字母。Mehrdad 是 Dokhtar-kosh 事物的爱好者 —— 若一个字符串经过字符重排后能形成回文串，则称其为 Dokhtar-kosh 字符串。

他向 Arpa 提问：对于每个顶点 $v$，其子树中能形成 Dokhtar-kosh 字符串的最长简单路径的长度是多少？

输入格式

第一行包含整数 $n$（$1 ≤ n ≤ 5×10^5$）——树中顶点个数。

随后 $n-1$ 行，第 $i$ 行包含一个整数 $p_{i+1}$ 和一个小写字母 $c_{i+1}$（$1 ≤ p_{i+1} ≤ i$，$c_{i+1}$ 介于字符 a 到 v 之间），表示在节点 $p_{i+1}$ 与节点 $i+1$ 之间存在一条边，且该边上的字母为 $c_{i+1}$。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示以第 $i$ 个顶点为根的子树中能形成 Dokhtar-kosh 字符串的最长简单路径的长度。

样例

4
1 s
2 a
3 s

3 1 1 0 

5
1 a
2 h
1 a
4 h

4 1 0 1 0