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;
const int MOD = 1e9 + 7;
const int C = 26;
void add(int& x, int y) {
  x += y;
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
}
int fix(int x) {
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
  return x;
}
int pw(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % MOD;
    b >>= 1;
    a = 1ll * a * a % MOD;
  }
  return ret;
}
const int MAXN = 5e5 + 10;
int n, ans[MAXN], sz[MAXN], in[MAXN], out[MAXN], at[MAXN], dep[MAXN],
    mask[MAXN], T, y;
vector<pair<int, int> > g[MAXN];
unordered_map<int, int>* dp[MAXN];
void dfs_pre(int u) {
  in[u] = T;
  at[T++] = u;
  sz[u] = 1;
  for (auto [v, ch] : g[u]) {
    dep[v] = dep[u] + 1;
    mask[v] = mask[u] ^ 1 << ch;
    dfs_pre(v);
    sz[u] += sz[v];
  }
  out[u] = T;
}
void dfs(int u) {
  int big = -1;
  for (auto& [v, _] : g[u])
    if (big == -1 || sz[v] > sz[big]) big = v;
  for (auto& [v, _] : g[u]) {
    if (v ^ big) {
      dfs(v);
      ans[u] = max(ans[u], ans[v]);
    }
  }
  if (~big) {
    dfs(big);
    dp[u] = dp[big];
    ans[u] = max(ans[u], ans[big]);
    ans[u] = max(ans[u], 1);
  } else {
    dp[u] = new unordered_map<int, int>;
  }
  for (auto& [v, _] : g[u]) {
    if (v ^ big) {
      for (int t = in[v]; t < out[v]; t++) {
        int w = at[t];
        if ((*dp[u]).count(mask[w] ^ y)) {
          ans[u] = max(ans[u], (*dp[u])[mask[w] ^ y] + dep[w] - 2 * dep[u]);
        }
        for (int b = 0; b < 22; b++) {
          if ((*dp[u]).count(mask[w] ^ y ^ 1 << b)) {
            ans[u] = max(ans[u],
                         (*dp[u])[mask[w] ^ y ^ 1 << b] + dep[w] - 2 * dep[u]);
          }
        }
      }
      for (int t = in[v]; t < out[v]; t++) {
        int w = at[t];
        (*dp[u])[mask[w] ^ y] = max((*dp[u])[mask[w] ^ y], dep[w]);
      }
    }
  }
  if ((*dp[u]).count(mask[u] ^ y)) {
    ans[u] = max(ans[u], (*dp[u])[mask[u] ^ y] - dep[u]);
  }
  for (int b = 0; b < 22; b++) {
    if ((*dp[u]).count(mask[u] ^ y ^ 1 << b)) {
      ans[u] = max(ans[u], (*dp[u])[mask[u] ^ y ^ 1 << b] - dep[u]);
    }
  }
  (*dp[u])[mask[u] ^ y] = max((*dp[u])[mask[u] ^ y], dep[u]);
}
void solve() {
  cin >> n;
  for (int i = 1; i < n; i++) {
    int p;
    cin >> p;
    char ch;
    cin >> ch;
    g[--p].emplace_back(i, ch - 'a');
  }
  dfs_pre(0);
  dfs(0);
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  y = rng() % (1 << 31);
  int te = 1;
  for (int w = 1; w <= te; w++) {
    solve();
  }
  return 0;
}
