 |
 |
 |
Problem # 25 : Sharing News
A group of people need to know a particular piece of information. People can only communicate with others within the group whom they know how to contact. They communicate through sending notes so someone can communicate with all the people that they know at once which takes up one time interval. Possible communication can be one-way; one person knows how to contact the other but not vice-versa.
You are given (in a text file) complete data about who each person can contact and which person originally had the information to distribute. Determine when each person gets the information. The person who originally has it gets it at time interval 0 the people he tells get it at time interval 1 and the people they tell get it at time interval 2 and so on.
Note that it is possible that a particular person may not be contacted and may never receive the information. List them as never .
The contacting data for the group will be in the following form : The first line of the file is an integer indicating the number of people in the group (N). The second line of input indicates the person who has the information to distribute. The remaining lines contain pairs of integers - a b indicating that the first member of the pair (a) can contact the second member of the pair (b). (Note a pair (a b) does not mean that (b) can contact (a)). The people are numbered from 1 thru N.
Sample Output
|
5 2 1 4 5 3 1 2 2 1 3 1 2 5 5 2 |
1 : Time interval 1 2 : Time interval 0 3 : Time interval 2 4 : Time interval 2 5 : Time interval 1 |
|
|
|