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;
int inf_int = 1e9;
bool debug = 0;
const int MAXN = 5e5 + 5;
vector<int> g[MAXN];
vector<char> g1[MAXN];
vector<int> g2[MAXN];
int siz[MAXN];
int mask[MAXN];
unordered_map<int, int> mp;
int dp[1 << 20];
int h[MAXN];
int st[MAXN], ft[MAXN];
int timer;
int ver[MAXN];
void dfs(int v, int p) {
  siz[v]++;
  st[v] = timer;
  ver[timer] = v;
  timer++;
  for (int i = 0; i < g[v].size(); ++i) {
    int to = g[v][i];
    char let = g1[v][i];
    if (to != p) {
      mask[to] = mask[v] ^ (1 << let);
      ;
      h[to] = h[v] + 1;
      dfs(to, v);
      siz[v] += siz[to];
    }
  }
  ft[v] = timer;
}
int ans[MAXN];
int id[MAXN];
int root, hroot;
void update(int v) {
  for (int to : g2[v]) {
    if (ans[root] < dp[to] + h[v] - hroot) ans[root] = dp[to] + h[v] - hroot;
  }
}
void dfs(int v, int p, bool save) {
  int mx = -1, big = -1;
  for (int to : g[v]) {
    if (to == p) continue;
    if (siz[to] > mx) {
      mx = siz[to];
      big = to;
    }
  }
  for (int to : g[v]) {
    if (to == p || to == big) continue;
    dfs(to, v, 0);
    ans[v] = max(ans[v], ans[to]);
  }
  if (big != -1) {
    dfs(big, v, 1);
    ans[v] = max(ans[v], ans[big]);
  }
  root = v;
  hroot = h[v] << 1;
  update(v);
  dp[id[v]] = max(dp[id[v]], h[v]);
  for (int to : g[v]) {
    if (to != p && to != big) {
      for (int i = st[to]; i < ft[to]; ++i) {
        update(ver[i]);
      }
      for (int i = st[to]; i < ft[to]; ++i) {
        dp[id[ver[i]]] = max(dp[id[ver[i]]], h[ver[i]]);
      }
    }
  }
  if (!save) {
    for (int i = st[v]; i < ft[v]; ++i) {
      dp[id[ver[i]]] = -inf_int;
    }
  }
}
void solve() {
  int n;
  cin >> n;
  for (int i = 2; i <= n; i++) {
    int p;
    char c;
    cin >> p >> c;
    c = c - 'a';
    g1[p].push_back(c);
    g[p].push_back(i);
  }
  dfs(1, 1);
  mp.reserve(1 << 20);
  mp.max_load_factor(0.25);
  for (int i = 1; i <= n; i++) {
    if (mp.count(mask[i]) == 0) {
      mp[mask[i]] = i;
      dp[i] = -inf_int;
    }
    id[i] = mp[mask[i]];
  }
  int m;
  int new_mask;
  for (int i = 1; i <= n; i++) {
    g2[i].push_back(id[i]);
    for (int e = 0; e < 26; e++) {
      new_mask = mask[i] ^ (1 << e);
      if (mp.count(new_mask)) {
        g2[i].push_back(mp[new_mask]);
      }
    }
  }
  dfs(1, 1, 1);
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
}
int main() {
  if (!debug) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  }
  int t = 1;
  while (t--) solve();
  return 0;
}
