#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cassert>
std::vector<int> slow(int n, std::vector<std::pair<int, char>> input) {
std::vector<char> cost(1+n);
std::vector<int> answ(1+n);
std::vector<std::vector<int>> edges(1+n);
// Edges from input vector:
for (int u = 2; u <= n; ++u) {
int p = input[u].first;
cost[u] = input[u].second;
edges[p].push_back(u);
edges[u].push_back(p);
}
// DFS function:
std::function<std::string(int,int)> visit = [&](int u, int p) {
std::string best; int r = u;
for (int v : edges[u]) {
if (v == p) continue;
auto temp = cost[v] + visit(v, u); // get string from child
if (temp.size() > best.size()) { // comparison this string with best string at this moment
best = temp;
r = v;
} else if (temp.size() == best.size()) {
if (temp > best || (temp == best && answ[v] < answ[r])) {
best = temp;
r = v;
}
}
}
answ[u] = (r == u) ? r : answ[r];
return best;
};
visit(1,0); // run dfs from root
// Return answer
for (int u = 1; u <= n; ++u) {
if (answ[u] == u) answ[u] = 0;
}
return answ;
}
std::vector<std::pair<int, char>> input(int& n) {
scanf("%d", &n);
std::vector<std::pair<int, char>> answ(1+n);
for (int u = 2; u <= n; ++u) {
int p; char c;
scanf("%d %c", &p, &c);
answ[u] = std::make_pair(p,c);
}
return answ;
}
int main() {
int n;
auto in = input(n);
auto answ = slow(n, in);
for (int u = 1; u <= n; ++u) {
printf("%d\n", answ[u]);
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDxjYXNzZXJ0PgoKc3RkOjp2ZWN0b3I8aW50PiBzbG93KGludCBuLCBzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8aW50LCBjaGFyPj4gaW5wdXQpIHsKICAgIHN0ZDo6dmVjdG9yPGNoYXI+IGNvc3QoMStuKTsKICAgIHN0ZDo6dmVjdG9yPGludD4gYW5zdygxK24pOwogICAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8aW50Pj4gZWRnZXMoMStuKTsKICAgIC8vIEVkZ2VzIGZyb20gaW5wdXQgdmVjdG9yOgogICAgZm9yIChpbnQgdSA9IDI7IHUgPD0gbjsgKyt1KSB7CiAgICAgICAgaW50IHAgPSBpbnB1dFt1XS5maXJzdDsgCiAgICAgICAgY29zdFt1XSA9IGlucHV0W3VdLnNlY29uZDsKICAgICAgICBlZGdlc1twXS5wdXNoX2JhY2sodSk7CiAgICAgICAgZWRnZXNbdV0ucHVzaF9iYWNrKHApOwogICAgfQogICAgLy8gREZTIGZ1bmN0aW9uOgogICAgc3RkOjpmdW5jdGlvbjxzdGQ6OnN0cmluZyhpbnQsaW50KT4gdmlzaXQgPSBbJl0oaW50IHUsIGludCBwKSB7CiAgICAgICAgc3RkOjpzdHJpbmcgYmVzdDsgaW50IHIgPSB1OwogICAgICAgIGZvciAoaW50IHYgOiBlZGdlc1t1XSkgewogICAgICAgICAgICBpZiAodiA9PSBwKSBjb250aW51ZTsKICAgICAgICAgICAgYXV0byB0ZW1wID0gY29zdFt2XSArIHZpc2l0KHYsIHUpOyAvLyBnZXQgc3RyaW5nIGZyb20gY2hpbGQKICAgICAgICAgICAgaWYgKHRlbXAuc2l6ZSgpID4gYmVzdC5zaXplKCkpIHsgLy8gY29tcGFyaXNvbiB0aGlzIHN0cmluZyB3aXRoIGJlc3Qgc3RyaW5nIGF0IHRoaXMgbW9tZW50CiAgICAgICAgICAgICAgICBiZXN0ID0gdGVtcDsKICAgICAgICAgICAgICAgIHIgPSB2OwogICAgICAgICAgICB9IGVsc2UgaWYgKHRlbXAuc2l6ZSgpID09IGJlc3Quc2l6ZSgpKSB7CiAgICAgICAgICAgICAgICBpZiAodGVtcCA+IGJlc3QgfHwgKHRlbXAgPT0gYmVzdCAmJiBhbnN3W3ZdIDwgYW5zd1tyXSkpIHsKICAgICAgICAgICAgICAgICAgICBiZXN0ID0gdGVtcDsKICAgICAgICAgICAgICAgICAgICByID0gdjsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBhbnN3W3VdID0gKHIgPT0gdSkgPyByIDogYW5zd1tyXTsKICAgICAgICByZXR1cm4gYmVzdDsKICAgIH07CiAgICB2aXNpdCgxLDApOyAvLyBydW4gZGZzIGZyb20gcm9vdAogICAgLy8gUmV0dXJuIGFuc3dlcgogICAgZm9yIChpbnQgdSA9IDE7IHUgPD0gbjsgKyt1KSB7CiAgICAgICAgaWYgKGFuc3dbdV0gPT0gdSkgYW5zd1t1XSA9IDA7CiAgICB9CiAgICByZXR1cm4gYW5zdzsKfQoKc3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgY2hhcj4+IGlucHV0KGludCYgbikgewogICAgc2NhbmYoIiVkIiwgJm4pOwogICAgc3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgY2hhcj4+IGFuc3coMStuKTsKICAgIGZvciAoaW50IHUgPSAyOyB1IDw9IG47ICsrdSkgewogICAgICAgIGludCBwOyBjaGFyIGM7CiAgICAgICAgc2NhbmYoIiVkICVjIiwgJnAsICZjKTsKICAgICAgICBhbnN3W3VdID0gc3RkOjptYWtlX3BhaXIocCxjKTsKICAgIH0KICAgIHJldHVybiBhbnN3Owp9CgppbnQgbWFpbigpIHsKICAgIGludCBuOwogICAgYXV0byBpbiA9IGlucHV0KG4pOwogICAgYXV0byBhbnN3ID0gc2xvdyhuLCBpbik7CiAgICBmb3IgKGludCB1ID0gMTsgdSA8PSBuOyArK3UpIHsKICAgICAgICBwcmludGYoIiVkXG4iLCBhbnN3W3VdKTsKICAgIH0KICAgIHJldHVybiAwOwp9