TAP2014E  Erdos et al
[ The original version of this problem (in Spanish) can be found at http://dc.uba.ar/events/icpc/download/problems/tap2014problems.pdf ]
Paul Erdös was a Hungarian mathematician of the 20th century who reached the highest levels of recognition. So much so that it is considered an honour not only having written an article with him, but also having shared authorship of a publication with one of his coauthors. Moreover, writing an article with someone who wrote an article with someone who wrote an article with Erdös is an important aspiration of many young researchers.
A natural consequence of such honours assignment, at least within the context of formal sciences, is the emergence of Erdös numbers. Erdös is the only person with an Erdös number of 0, and for any other person p, his/her Erdös number n is defined by the shortest sequence of articles a_{1}, ... , a_{n} such that Erdös is one of the authors of article a_{1}, p is one the authors of article a_{n}, and every pair of consecutive articles a_{i} and a_{i+1 }(for i = 1, 2, ..., N1) have at least one author in common. If no sequence of articles linking Erdös and p exists, we shall say that p's Erdös number is undefined.
Your task in this problem is to compute Erdös numbers based only on a corpus of articles and authors given as input. Unfortunately, current science demands scientists to increase very rapidly the number of articles they write, causing both the total number of articles and the number of authors per article to be huge. Of course, this reality is an obstacle that a correct solution to this problem should be able to handle.
Your task in this problem is to compute Erdös numbers based only on a corpus of articles and authors given as input. Unfortunately, current science demands scientists to increase very rapidly the number of articles they write, causing both the total number of articles and the number of authors per article to be huge. Of course, this reality is an obstacle that a correct solution to this problem should be able to handl
Input
The first line contains two integers A and N, where A represents the number of articles in the corpus to be analysed and N the number of people who appear in it (where 2 ≤ A, N ≤ 10^{5}). People are identified with integers between 1 and N, and Erdös will always be the person identified with number 1.
Each of the following A lines describes an article. Each of these lines begins with an integer C representing the number of authors of the article (2 ≤ C ≤ 10^{5}), and then there are C distinct integers P_{1}, P_{2}, ... , P_{C} representing the identifiers of the authors of the article (1 ≤ P_{i} ≤ N for i = 1, 2, ... , C). The sum of the number of authors over all articles does not exceed 10^{5}.
Output
For each test case you must print three integers D, M and S, where D represents the number of people on the corpus who have a welldefined Erdös number, M is the maximum Erdös number of one of those people and S is the sum of all the Erdös numbers belonging to people who have a welldefined Erdös number.
Example 1
Input: 3 5 2 1 5 3 5 2 3 3 3 2 4 Output: 5 3 8
Example 2
Input: 5 11 2 10 11 4 1 3 5 7 6 2 3 4 5 6 7 4 3 5 7 9 3 8 1 5 Output: 9 2 12
Example 3
Input: 6 31 9 1 2 3 15 20 25 30 9 10 10 2 25 7 9 3 11 12 13 14 4 10 11 12 13 14 4 16 17 18 19 5 2 5 7 9 21 22 23 24 26 27 28 29 7 3 22 6 21 Output: 29 4 63
hide comments
julkas:
20180728 13:54:39
Great problem. 

nadstratosfer:
20180721 22:50:39
Note that Erdös has a welldefined Erdös number even if there are no papers he coauthored. 

gamer496:
20150626 08:09:21
Good ques 

Francky:
20150527 01:33:31
@Candide : well done ;) 

candide:
20150527 01:32:26
@francky: thx ;) Last edit: 20150527 06:51:25 

fitcat:
20141020 05:17:44
My 800th classical problem solved :) 
Added by:  Fidel Schaposnik 
Date:  20140929 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Argentinian Programming Tournament 2014 