|
|||
Spreading the NewsIn a large organization, everyone knows a lot of colleagues. However, friendship relations are kept with only a few of them, to whom news is 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:
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. Input SpecificationThe 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 (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. Two consecutive 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. Output SpecificationThe 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. Sample Input
Output for Sample Input
|
|||
| University of Debrecen; Faculty of Informatics; v. 09/30/2024 |