SP21172 TAP2014E - Erdos et al

**\[ The original version of this problem (in Spanish) can be found at [http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf](http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.pdf "http://dc.uba.ar/events/icpc/download/problems/tap2014-problems.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 co-authors. 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, ..., N-1**) 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. 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 honor not only having written an article with him, but also having shared autorship of a publication with one of his co-authors. 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.

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 ****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} $** .********

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 well-defined 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 well-defined Erdös number.