In a large organization, everyone knows a lot of colleagues. However, friendship relations are kept with only a few of them, to whom news are told.
Suppose that whenever an employee knows of a piece of news, he tells it to all his friends on the following day. So, on the first day, the source of the information tells it to his friends; on the second day, the source’s friends tell it to their friends; on the third day, the friends of the source’s friends’ tell it to their friends; and so on.
The goal is to determine:
· the maximum daily boom size, which is the largest number of employees that, on a single day, hear the piece of news for the first time; and
· the first boom day, which is the first day on which the maximum daily boom size occurs.
Write a program that, given the friendship relations between the employees and the source of a piece of news, computes the maximum daily boom size and the first boom day of that information spreading process.
The first line of the input contains the number E of employees (1 <= E <= 2500). Employees are numbered from 0 to E-1.
Each of the following E lines specifies the set of friends of an employee’s (from employee 0 to employee E-1). A set of friends contains the number of friends N (0 <= N < 15), followed by N distinct integers representing the employee’s friends. All integers are separated by a single space.
The next line contains an integer T (1 <= T < 60), which is the number of test cases.
Each of the following T lines contains an employee, which represents the (unique) source of the piece of news in the test case.
The output consists of T lines, one for each test case.
If no employee (but the source) hears the piece of news, the output line contains the integer 0.
Otherwise, the output line contains two integers, M and D, separated by a single space, where M is the maximum daily boom size and D is the first boom day.
6
2 1 2
2 3 4
3 0 4 5
1 4
0
2 0 2
3
0
4
5
3 2
0
2 1
MIUP'2004: Fourth Portuguese National Programming
Contest