Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Counting Friends

By TarifEzaz · Limits 1s, 512 MB

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 NN 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 NN interactions with him in Supernova.

You are building a social network yourself and want to imitate this feature. Given NN interactions in the form aa bb, where aa and bb 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 NN ( 1N10001 ≤ N ≤ 1000 ), the number of interactions in the social network.

Each of the next NN lines will have two integers aa bb ( 1a,b10001 ≤ a, b ≤ 1000, aba \neq b ), where aa and bb are the identifiers of two users.

Output

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

Sample

InputOutput
3
1 2
2 3
1 3
2
2
2

Discussion

Statistics


66% Solution Ratio

NirjhorEarliest, 1M ago

EdgedancerFastest, 0.0s

zahidILightest, 131 kB

alamkhanShortest, 273B

Submit

Login to submit

Editorial

For each person, it is required to keep the number of unique interactions. For that, we can use a tw...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.