Problem D
Erdős Numbers

Paul Erdős (1913-1996) was a very prolific Hungarian mathematician. He is famous for the amount of mathematics he produced (about $1\, 475$ papers published during his lifetime), the number of professional collaborators and coauthors he worked with (he had $511$ coauthors), and his nomadic lifestyle. He routinely traveled to visit collaborators, staying with them long enough to work on a few ideas, before moving on to visit someone else. Whenever he encountered a mathematical proof he thought was particularly elegant, he would claim it came from “The Book” – a special volume in which he believed God kept all the best proofs of every mathematical theorem.

Erdős worked a lot on graph theory, which is concerned with the structure of connections between pairs of objects. Fittingly, we can treat the collaboration of mathematicians as a graph problem, where each person is represented by a graph node, and each coauthored paper forms edges between all pairs of nodes for the corresponding coauthors on the paper. Erdős  is directly connected with a lot of coauthors with whom he published papers, who are further connected to other coauthors by other publications, and so on. This has led to the concept of an Erdős  number. Erdős  himself has an Erdős  number of $0$. All of his coauthors have an Erdős  number of $1$. Everyone who is a coauthor with one of his coauthors (but not with Erdős  himself) has an Erdős  number of $2$, and so on. It’s become a matter of distinction to have a low Erdős  number.

Write a program to help people who have published papers find their Erdős  number – that is, the smallest number of coauthors linking them to Erdős.

Input

Input consists of one database of paper coauthorship, containing up to $2\, 000$ lines. Each line begins with an author’s name, followed by a space-separated list of $0$ to $511$ coauthor names. Note that some authors list a limited set of his/her coauthors; but two people are considered coauthors if either lists the other as a coauthor. Paul Erdős  is one of the listed authors (always given as PAUL_ERDOS). Every name consists of up to $40$ letters (a-z), hyphens, and underscores. Input ends at end of file.

Note: In the sample input, a limited set of Erdős  coauthors are listed for space reasons.

Output

For each author (the first name of each line in the input), print the author’s name and his or her Erdős  number. Print the authors in the same order they appear in the database. If some author has no connection to Erdős, print no-connection.

PAUL_ERDOS HARVEY_ABBOTT JANOS_ACZEL TAKASHI_AGOH RON_AHARONI MARTIN_AIGNER MIKLOS_AJTAI
HARVEY_ABBOTT CHARLES_AULL EZRA_BROWN PAUL_DIERKER
PAUL_DIERKER MATTS_ESSEN
FRANK_BROWN CHARLES_ROGERS

PAUL_ERDOS 0
HARVEY_ABBOTT 1
PAUL_DIERKER 2
FRANK_BROWN no-connection