Counting Friends

Johnny uses a social network called Supernova. Unlike the other social networks, Supernova does not give a direct count on the number of friends one user has. Instead, it keeps a track of the latest $N$ interactions of all the users. From these interactions, Supernova calculates the number of friends for each of the users. Thus, in order to be Johnny’s friend in Supernova, one must contribute to at least one of the latest $N$ interactions with him in Supernova.

You are building a social network yourself and want to imitate this feature. Given $N$ interactions in the form $a$ $b$, where $a$ and $b$ are two integers indicating two users of a social network, calculate the number of friends each of the users has.

Input

The first line of the input contains an integer $N$ ( $1 ≤ N ≤ 1000$ ), the number of interactions in the social network.

Each of the next $N$ lines will have two integers $a$ $b$ ( $1 ≤ a, b ≤ 1000$, $a \neq b$ ), where $a$ and $b$ are the identifiers of two users.

Output

In the output, print $X$ lines. Here, $X$ is the number of people who were active in the last $N$ interactions in the social network. In the $i-th$ line ( $1 ≤ i ≤ X$), print the number of friends the $i-th$ user has. The order of the users are found by sorting them in the increasing number of their original identifiers.

Sample

Input	Output
3 1 2 2 3 1 3	2 2 2