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.

<image>

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.

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 + 1 and a letter ci + 1 (1 ≤ pi + 1 ≤ i, ci + 1 is lowercase English letter, between a and v, inclusively), that mean that there is an edge between nodes pi + 1 and i + 1 and there is a letter ci + 1 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.

Examples

Input

4
1 s
2 a
3 s


Output

3 1 1 0 

Input

5
1 a
2 h
1 a
4 h


Output

4 1 0 1 0 
#include <bits/stdc++.h>
using namespace std;
void Read(int& p) {
  p = 0;
  char c = getchar();
  for (; c < '0' || c > '9'; c = getchar())
    ;
  for (; c >= '0' && c <= '9'; c = getchar()) p = p * 10 + c - '0';
}
int n, fir[500005], nex[500005], tar[500005], cnt;
int fat[500005], dep[500005], pre[500005], son[500005];
int ans[500005], siz[500005], bit[30], f[1 << 22];
char C[5];
void add(int a, int b) {
  ++cnt;
  tar[cnt] = b;
  nex[cnt] = fir[a];
  fir[a] = cnt;
}
void Chkmax(int& x, int y) { x = max(x, y); }
void Dfs1(int r) {
  siz[r] = 1;
  for (int i = fir[r]; i; i = nex[i]) {
    int v = tar[i];
    dep[v] = dep[r] + 1;
    pre[v] ^= pre[r];
    Dfs1(v);
    siz[r] += siz[v];
    if (siz[v] > siz[son[r]]) son[r] = v;
  }
}
void Calc(int r, int g) {
  for (int i = 0; i <= 22; i++) Chkmax(ans[g], dep[r] + f[pre[r] ^ bit[i]]);
  for (int i = fir[r]; i; i = nex[i]) Calc(tar[i], g);
}
void Add(int r) {
  Chkmax(f[pre[r]], dep[r]);
  for (int i = fir[r]; i; i = nex[i]) Add(tar[i]);
}
void Del(int r) {
  f[pre[r]] = -0x3f3f3f3f;
  for (int i = fir[r]; i; i = nex[i]) Del(tar[i]);
}
void Dfs2(int r) {
  for (int i = fir[r]; i; i = nex[i])
    if (tar[i] != son[r]) Dfs2(tar[i]), Del(tar[i]);
  if (son[r]) Dfs2(son[r]);
  Chkmax(f[pre[r]], dep[r]);
  for (int i = 0; i <= 22; i++) Chkmax(ans[r], dep[r] + f[pre[r] ^ bit[i]]);
  for (int i = fir[r]; i; i = nex[i])
    if (tar[i] != son[r]) Calc(tar[i], r), Add(tar[i]);
}
int main() {
  Read(n);
  for (int i = 2; i <= n; i++) {
    Read(fat[i]);
    scanf("%s", C);
    add(fat[i], i);
    pre[i] = 1 << (C[0] - 'a');
  }
  for (int i = 0; i < (1 << 22); i++) f[i] = -0x3f3f3f3f;
  for (int i = 0; i < 22; i++) bit[i] = 1 << i;
  Dfs1(1), Dfs2(1);
  for (int i = 1; i <= n; i++) ans[i] -= 2 * dep[i];
  for (int i = n; i >= 1; i--) Chkmax(ans[fat[i]], ans[i]);
  for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? 10 : 32);
}
