以防万一有人错过了:我们在阿尔帕的土地上有很棒的女孩。
Arpa 有一个由 n 个顶点组成的有根树(连通无环图)。顶点编号为 1 到 n,顶点 1 是根。这棵树的每条边上都写着一封信。迈赫达德是 Dokhtar-kosh 事物的粉丝。如果我们可以将字符串中的字符打乱,使其成为回文,他将字符串称为 Dokhtar-kosh。
他问Arpa,对于每个顶点v,v的子树中形成Dokhtar-kosh字符串的最长简单路径的长度是多少。
输入
第一行包含整数 n (1 ≤ n ≤ 5·105) — 树中的顶点数。 接下来是
(n - 1) 行,其中第 i 行包含一个整数 pi + 1 和一个字母 ci + 1(1 ≤ pi + 1 ≤ i,ci + 1 为小写英文字母,介于 a 和 v 之间),这意味着节点 pi + 1 和 i + 1 之间有一条边,并且这条边上写有一个字母 ci + 1。
输出
打印 n 个整数。其中第 i 个应该是形成 Dokhtar-kosh 字符串的第 i 个顶点的子树中最长的简单路径的长度。
示例
输入 #1
4 1 s 2 a 3 s
输出 #1
3 1 1 0
输入 #2
5 1 a 2 h 1 a 4 h
输出 #2
4 1 0 1 0