import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.string;
 
void main ()
{
	int n;
	while (readf (" %s", &n) > 0)
	{
		auto p = new int [n];
		auto c = new char [n];
		auto a = new int [] [n];
		foreach (i; 1..n)
		{
			readf (" %s %s", &p[i], &c[i]);
			p[i] -= 1;
			a[p[i]] ~= i;
		}
 
		auto vis = new bool [n];
		auto dist = new int [n];
		auto next = new int [n];
		auto term = new int [n];
		term = n.iota.array;
		next[] = -1;
 
		bool less (int u, int v)
		{
			bool cur = false;
			do
			{
				if (c[u] != c[v])
				{
					return c[u] > c[v];
				}
				cur = (u < v);
				u = next[u];
				v = next[v];
			}
			while (u != -1);
			return cur;
		}
 
		void recur (int v)
		{
			if (vis[v])
			{
				return;
			}
			vis[v] = true;
 
			foreach (u; a[v])
			{
				recur (u);
				int cand = dist[u] + 1;
				if (dist[v] < cand || (dist[v] == cand &&
				    less (u, next[v])))
				{
					dist[v] = cand;
					next[v] = u;
					term[v] = term[u];
				}
			}
			debug {writeln (v, ": ", dist[v], " ",
			    next[v], " ", term[v]);}
		}
 
		foreach (i; 0..n)
		{
			if (!vis[i])
			{
				recur (i);
			}
			writeln (dist[i] > 0 ? term[i] + 1 : 0);
		}
	}
}
 

aW1wb3J0IHN0ZC5hbGdvcml0aG07CmltcG9ydCBzdGQuY29udjsKaW1wb3J0IHN0ZC5yYW5nZTsKaW1wb3J0IHN0ZC5zdGRpbzsKaW1wb3J0IHN0ZC5zdHJpbmc7Cgp2b2lkIG1haW4gKCkKewoJaW50IG47Cgl3aGlsZSAocmVhZGYgKCIgJXMiLCAmbikgPiAwKQoJewoJCWF1dG8gcCA9IG5ldyBpbnQgW25dOwoJCWF1dG8gYyA9IG5ldyBjaGFyIFtuXTsKCQlhdXRvIGEgPSBuZXcgaW50IFtdIFtuXTsKCQlmb3JlYWNoIChpOyAxLi5uKQoJCXsKCQkJcmVhZGYgKCIgJXMgJXMiLCAmcFtpXSwgJmNbaV0pOwoJCQlwW2ldIC09IDE7CgkJCWFbcFtpXV0gfj0gaTsKCQl9CgoJCWF1dG8gdmlzID0gbmV3IGJvb2wgW25dOwoJCWF1dG8gZGlzdCA9IG5ldyBpbnQgW25dOwoJCWF1dG8gbmV4dCA9IG5ldyBpbnQgW25dOwoJCWF1dG8gdGVybSA9IG5ldyBpbnQgW25dOwoJCXRlcm0gPSBuLmlvdGEuYXJyYXk7CgkJbmV4dFtdID0gLTE7CgoJCWJvb2wgbGVzcyAoaW50IHUsIGludCB2KQoJCXsKCQkJYm9vbCBjdXIgPSBmYWxzZTsKCQkJZG8KCQkJewoJCQkJaWYgKGNbdV0gIT0gY1t2XSkKCQkJCXsKCQkJCQlyZXR1cm4gY1t1XSA+IGNbdl07CgkJCQl9CgkJCQljdXIgPSAodSA8IHYpOwoJCQkJdSA9IG5leHRbdV07CgkJCQl2ID0gbmV4dFt2XTsKCQkJfQoJCQl3aGlsZSAodSAhPSAtMSk7CgkJCXJldHVybiBjdXI7CgkJfQoKCQl2b2lkIHJlY3VyIChpbnQgdikKCQl7CgkJCWlmICh2aXNbdl0pCgkJCXsKCQkJCXJldHVybjsKCQkJfQoJCQl2aXNbdl0gPSB0cnVlOwoKCQkJZm9yZWFjaCAodTsgYVt2XSkKCQkJewoJCQkJcmVjdXIgKHUpOwoJCQkJaW50IGNhbmQgPSBkaXN0W3VdICsgMTsKCQkJCWlmIChkaXN0W3ZdIDwgY2FuZCB8fCAoZGlzdFt2XSA9PSBjYW5kICYmCgkJCQkgICAgbGVzcyAodSwgbmV4dFt2XSkpKQoJCQkJewoJCQkJCWRpc3Rbdl0gPSBjYW5kOwoJCQkJCW5leHRbdl0gPSB1OwoJCQkJCXRlcm1bdl0gPSB0ZXJtW3VdOwoJCQkJfQoJCQl9CgkJCWRlYnVnIHt3cml0ZWxuICh2LCAiOiAiLCBkaXN0W3ZdLCAiICIsCgkJCSAgICBuZXh0W3ZdLCAiICIsIHRlcm1bdl0pO30KCQl9CgoJCWZvcmVhY2ggKGk7IDAuLm4pCgkJewoJCQlpZiAoIXZpc1tpXSkKCQkJewoJCQkJcmVjdXIgKGkpOwoJCQl9CgkJCXdyaXRlbG4gKGRpc3RbaV0gPiAwID8gdGVybVtpXSArIDEgOiAwKTsKCQl9Cgl9Cn0K

NgoxIGIKMiBjCjEgYgo0IGQKNSBlCgo2CjEgYgoyIGQKMSBiCjQgYwo1IGUKCjEKCjUKMSBiCjIgYwoxIGIKNCBkCgo1CjEgYgoyIGQKMSBiCjQgYwoKNQoxIGIKMSBiCjMgYwozIGEK

6
1 b
2 c
1 b
4 d
5 e

6
1 b
2 d
1 b
4 c
5 e

1

5
1 b
2 c
1 b
4 d

5
1 b
2 d
1 b
4 c

5
1 b
1 b
3 c
3 a