D. Equal Vertices
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Compare all vertices of a finite vertex-labeled directed graph in which every vertex has at most one outgoing edge.

Two vertices are equal if they cannot be distinguished by the following process:

  1. Compare labels. Whenever they differ, the process stops and reports vertices are not equal.
  2. Compare outgoing degrees. Whenever they differ, the process stops and reports vertices are not equal.
  3. When both vertices have no outgoing edges, the process stops and reports vertices are equal.
  4. Follow outgoing edges and repeat the process.

Please note, when the process reports vertices are equal, it implies that vertices cannot be distinguished.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$): the number of vertices.

The following $$$n$$$ lines describe vertices. Each description contains a lowercase English letter (vertex label) and number $$$t$$$ separated by space. $$$t = 0$$$ means that vertex has no outgoing edges. Otherwise, it has an edge to $$$t$$$-th vertex. Vertices are numbered from $$$1$$$ to $$$n$$$ in the order they given.

Output

Output exactly $$$n$$$ lines.

On the $$$i$$$-th line write the equality class number of the $$$i$$$-th vertex. Equal vertices should have the same class number.

Classes are numbered as follows: the first vertex belongs to the first class, the next vertex that doesn't belong to the first class belongs to the second class, and so on.

Example
Input
4
a 2
b 3
b 0
b 3
Output
1
2
3
2