Social Network Influence Score

You are given a social network represented by follow relationships. Each follow relationship is a directed edge where user u follows user v. The influence score of a user is defined as the number of users (excluding the user itself) that can reach this user by following a chain of follow relationships. In other words, for a given user i, count the number of users that (directly or indirectly) follow i.

The input begins with an integer indicating the number of follow relationships, followed by that many lines, each containing two integers u and v representing that user u follows user v. Note that the user IDs are positive integers and they might not be consecutive; however, you should consider all user IDs from 1 to the maximum user ID encountered.

Your task is to calculate the influence score for every user from 1 to the maximum user ID. Use a breadth-first search (BFS) on the reverse graph (i.e. from a user, move to all users who follow him/her) to count the number of users that can indirectly or directly reach each user.

Note: When a user follows themselves, do not count the user in its own influence score.

inputFormat

The first line of input contains a single integer M, denoting the number of follow relationships. Each of the following M lines contains two space-separated integers u and v, indicating that user u follows user v.

outputFormat

For each user from 1 to the maximum user ID encountered in the input, print a line with two integers: the user ID and its corresponding influence score, separated by a space.## sample

5
1 2
2 3
3 4
4 5
1 3

1 0
2 1
3 2
4 3
5 4