Amoeba is a good friend of Xiaoqiang.

Amoeba and Xiaoqiang are catching grasshoppers on the prairie. Xiaoqiang suddenly wonders: if they catch all the grasshoppers to extinction, the birds that eat grasshoppers will starve to death, and the raptors that prey on those birds will also go extinct, thus triggering a series of ecological disasters.

Amoeba, who has studied biology, tells Xiaoqiang that the prairie is an extremely stable ecosystem. If grasshoppers go extinct, birds can still eat other insects, so the extinction of one species does not necessarily trigger a major disaster.

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

A food web has $N$ nodes, representing $N$ species. If organism $x$ can eat organism $y$, there is a directed edge from $y$ to $x$.

This graph has no cycles.

Some nodes in the graph have no outgoing edges; these nodes represent producers, which can survive through photosynthesis. Nodes with outgoing edges represent consumers, which must survive by eating other organisms.

If all the food sources of a consumer go extinct, it will also go extinct.

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 were to suddenly go extinct.

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

If Xiaoqiang and Amoeba scare all the sheep on the prairie to death, the wolves will go extinct due to a lack of food, while Xiaoqiang and Amoeba can survive by eating cows, and cows can survive by eating grass. Therefore, the disaster value of a sheep is 1. However, if the grass suddenly goes extinct, all 5 species on the entire prairie cannot be spared, so the disaster value of the grass is 4.

Given a food web, you are required to calculate the disaster value for each organism.

Input

The first line contains a positive integer $N$, representing the number of species. The species are numbered from $1$ to $N$.

The next $N$ lines each describe the list of other organisms that a species can eat. The format consists of several space-separated numbers, where each number represents the ID of an organism, and the last number is $0$, indicating the end of the list.

Output

The output contains $N$ lines, each containing an integer representing the disaster value of each organism.

Examples

Input 1

5 
0 
1 0 
1 0 
2 3 0 
2 0

Output 1

4 
1 
0 
0 
0

Note 1

The sample input describes the example given in the problem statement.

Constraints

For 50% of the data, $N \le 10000$. For 100% of the data, $1 \le N \le 65534$. The size of the input file does not exceed 1MB. It is guaranteed that the input food web has no cycles.