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 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 interactions with him in Supernova.
You are building a social network yourself and want to imitate this feature. Given interactions in the form , where and are two integers indicating two users of a social network, calculate the number of friends each of the users has.
The first line of the input contains an integer ( ), the number of interactions in the social network.
Each of the next lines will have two integers ( , ), where and are the identifiers of two users.
In the output, print lines. Here, is the number of people who were active in the last interactions in the social network. In the line ( ), print the number of friends the user has. The order of the users are found by sorting them in the increasing number of their original identifiers.
Input | Output |
---|---|
3 1 2 2 3 1 3 | 2 2 2 |