# Problem C

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

Sample Input 1 | Sample Output 1 |
---|---|

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 |