Nosaukums
Sešas atsvešināšanās pakāpes (sixdegrees)
Laika limits
0.50s
Atmiņas limits
64.0 MB
Grūtība
63%

Definīcija

Sešas atsvešināšanās pakāpes ir ideja, ka jebkuriem diviem cilvēkiem ir kopīgs "drauga draugs" līdz 6 draugu attālumā. Piemēram, ja ir seši cilvēki - Jānis, Pēteris, Vladislavs, Mārtiņš, Eduards, Juris, Pauls - un viņi pazīst tikai sarakstā blakus esošos cilvēkus, tad attālums starp Jāni un Paulu ir 6.

Bet, ja šī attiecība nav abpusēja, šis skaitlis ir lielāks. Piemēram, Vladislavs izseko Eduardu un zina pārāk daudz par viņu, bet Eduards neko par Vadislavu nezina. 

Jūsu uzdevums ir, zinot cilvēku savstarpējās attiecības, atrast lielāko attālumu starp 2 cilvēkiem.

Skaitot attālumu starp 2 cilvēkiem, viens un tas pats cilvēks ķēdē neparādas vairāk kā vienu reizi.


Ievaddatu raksturojums

Pirmajā rindā dots n un m (1 <= n, m <= 10000) - cilvēku skaits un attiecību skaits.

Tālāk seko m rindiņas ar cilvēku vārdiem a un b, kuri apzīmē, ka a pazīst b. Cilvēka vārds satur ne vairāk kā 20 latīņu alfabēta simbolus un nesatur atstarpes.


Izvaddatu raksturojums

Jāizvada viens skaitlis - lielākais attālums starp 2 cilvēkiem.


Piezīmes

Dotajā piemērā 2 derīgas atbildes: Jānis-Pēteris-Mārtiņš-Juris vai Vadislavs-Eduards-Mārtiņš-Juris


Paraugdati

Stdin
6 5
Janis Peteris
Peteris Martins
Martins Juris
Eduards Martins
Vadislavs Eduards
Stdout
3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.