Erdös-nummer

Matematikern Paul Erdös är bl.a. känd för att vara den matematiker som skrivit flest matematiska publikationer (Leonhard Euler har dock flest skrivna sidor). Erdös samarbetade väldigt mycket i sina publikationer. Ociterade källor hävdar att han ofta var temporärt inneboende hos en kollega. Under besöken skrev han en publikation tillsammans med kollegan och när gästfriheten tog slut flyttade Erdös vidare till nästa kollega.

Det innebär stor prestige att ha skrivit en publikation med Erdös. De som har skrivit en publikation med Erdös definieras ha Erdös-nummer 1. Ifall man skrivit en publikation med en person med Erdös-nummer 1 så får man Erdös-nummer 2 o.s.v.

Givet en lista över publikationer, skriv ut en lista med alla inblandade matematikers Erdös-nummer.

1 Indata

Först raden innehåller två heltal, $1 \le N \le 5\, 000$ och $1 \le M \le 40\, 000$, antalet matematiker respektive antalet publikationer. Därefter följer $M$ rader. Varje rad börjar med ett heltal, antalet matematiker som samarbetade i publikationen. Sedan följer matematikernas namn (mellanslags-separerade), ordningen på matematikerna spelar ingen roll. Matematikernas namn består av 1 till 20 stora bokstäver, $A - Z$. Inga olika matematiker har samma namn. Erdös heter ERDOS. I varje publikation kommer det vara minst 2 och högst 5 matematiker. Du kan anta att Erdös-numret är ändligt för alla inblandade matematiker.

2 Utdata

En nyrads-separerad lista med matematiker och deras Erdös-nummer. ERDOS ska vara med i denna lista, hans Erdös-nummer är alltid 0. Listan ska vara sorterad i alfabetisk ordning.

5 4
2 ERDOS IMMERMAN
2 JACKSON IMMERMAN
3 ERDOS JACKSON IMMERMAN
3 BACH JACKSON RUBINSTEIN

BACH 2
ERDOS 0
IMMERMAN 1
JACKSON 1
RUBINSTEIN 2

10 10
2 ERDOS JYVZ
2 QHD DNJMFFHIVNTXOR
2 GXNVNYPG ERDOS
2 JYVZ DNJMFFHIVNTXOR
3 RIZTHDDFLKTKHLUMS GXNVNYPG AOFJAZXUBICBIIPP
2 LFX GXNVNYPG
2 GOGDYHYXDRHCKQHQV AOFJAZXUBICBIIPP
2 AOFJAZXUBICBIIPP QHD
3 NWLMBD AOFJAZXUBICBIIPP QHD
2 DNJMFFHIVNTXOR NWLMBD

AOFJAZXUBICBIIPP 2
DNJMFFHIVNTXOR 2
ERDOS 0
GOGDYHYXDRHCKQHQV 3
GXNVNYPG 1
JYVZ 1
LFX 2
NWLMBD 3
QHD 3
RIZTHDDFLKTKHLUMS 2