Title Details

https://www.lydsy.com/JudgeOnline/upload/zjoi2012.pdf

Title Description

Amoeba is a good friend of Xiaoqiang. Amoeba and Xiaoqiang are catching grasshoppers on the grassland. Xiaoqiang suddenly thought that if the grasshoppers were caught and extinct by them, the birds that eat grasshoppers would starve to death, and the raptors that prey on birds would also become extinct, triggering a series of ecological disasters.

Amoeba, who has studied biology, told Xiaoqiang that grassland is an extremely stable ecosystem. If leeches become extinct, birds can still eat other insects, so the extinction of a species does not necessarily lead to a major disaster

We are now looking at this issue from a more professional perspective. We use a directed graph called the food web to describe the relationships between organisms:

A food web has $N$ points representing $N$ species of organisms. If an organism $x$ can eat an organism $y$, then connect a directed edge from $y$ to $x$. This picture doesn't have a ring.

There are some points in the figure that are not connected by edges, representing organisms that are producers and can survive through photosynthesis; And the dots with edges represent consumers who must survive by eating other organisms.

If all of a consumer's food goes extinct, it will follow suit

We define the 'disaster value' of an organism in the food web as the number of species that would go extinct along with it if it suddenly went extinct.

For example, on a grassland, the relationships between organisms are:

If Xiaoqiang and Amoeba scared all the sheep on the grassland to death, the wolves would become extinct due to lack of food, while Xiaoqiang and Amoeba could survive by eating cows and cows could survive by eating grass. So, the disaster value for sheep is $1$. However, if grass suddenly becomes extinct, all five species of organisms on the entire grassland will not be spared, so the disaster value of grass is $4$.

Given a food web, you require the disaster value of each organism.

Input format

The first line of the input file catas. in is a positive integer $N$, representing the number of species of organisms. Biology is labeled from $1$ to $N$.

The next $N$ line describes a list of other organisms that a creature can eat, in the format of several numbers separated by spaces, each number representing the label of a creature, and the last number being $0$indicating the end of the list.

Output format

The output file catas. out contains $N$ lines, each line containing an integer representing the disaster value for each organism,

Example

5
0
1 0
1 0
2 3 0
2 0

4
1
0
0
0

Example Description

The example input describes the examples given in the title description.

Data scale and agreement

For data of $50\%$, $N\le 10000$.

For data of $100\%$, $1\le N\le 65534$.

The size of the input file should not exceed $1MB$, and the food web entered does not have a ring.