Nombre d'Erdős P50067

El professor Oak ha llegit l’article “And what is your Erdős number?”, on es va definir el nombre d’Erdős de la manera següent: Paul Erdős té nombre d’Erdős 0. Cadascun dels 509 col·laboradors amb qui va escriure els seus (prop de 1500!) articles té nombre d’Erdős 1. Les 6984 persones que van col·laborar amb els col·laboradors directes d’Erdős (però no amb Erdős mateix) tenen nombre d’Erdős 2, i així successivament. Les persones sense connexió en el graf de co-autoria d’Erdős tenen un nombre d’Erdős indefinit.

En el tradicional pica-pica de Nadal del departament, el professor Oak explica amb orgull a la resta de companys que després d’uns quants càlculs ha trobat que el seu nombre d’Erdős és 3. Immediatament, el professor Little li replica que no n’hi ha per tant, que ell també té nombre d’Erdős 3. En sentir la conversa, la professora Churches els fa notar que ella té nombre d’Erdős 2. D’aquesta manera s’organitza una competició per veure qui té el nombre d’Erdős més baix. Podeu ajudar-los?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre n d’investigadors, seguit de n cognoms diferents, seguit del nombre m de publicacions dels investigadors. Segueix la informació de cada publicació: el nombre de co-autors (entre dos i vuit) seguit de la llista dels diferents cognoms. Suposeu 1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, que els cognoms només tenen entre dues i vuit lletres minúscules, que no hi ha dues persones amb el mateix cognom, i que Erdős, si apareix, és com a “erdos”.

Sortida

Per a cada cas, escriviu el cognom dels n donats al principi que tingui el nombre d’Erdős més baix, i també aquest nombre. En cas d’empat, escriviu el cognom lexicogràficament més petit. Si cap dels n investigadors té nombre d’Erdős ben definit, escriviu “???”.