TAP2014E - Erdos et al

no tags 

[ The original version of this problem (in Spanish) can be found at 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 a1, ... , an such that Erdös is one of the authors of article a1, p is one the authors of article an, and every pair of consecutive articles ai and ai+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.
A natural consequence of such honors 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} 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 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  105). 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 ( C  105), and then there are C distinct integers P1, P2, ... , PC representing the identifiers of the authors of the article ( Pi  N for i = 1, 2, ... , C). The sum of the number of authors over all articles does not exceed 105.

 

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 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.

 

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
gamer496: 2015-06-26 08:09:21

Good ques

Francky: 2015-05-27 01:33:31

@Candide : well done ;-)

candide: 2015-05-27 01:32:26

@francky: thx ;)

Last edit: 2015-05-27 06:51:25
fitcat: 2014-10-20 05:17:44

My 800th classical problem solved :)


Added by:Fidel Schaposnik
Date:2014-09-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2014