Fa

A gráfelméletben fának vagy fagráfnak nevezzük azokat a gráfokat, amelynek bármely két csúcsát pontosan egy út köti össze, azaz a fák körmentes összefüggő gráfok. Tekintsük a következő fa reprezentációt: A fák csúcsait egyetlen karakter jelöli, mely egyedi. Jelölje XY karakter pár, hogy egy adott fában X csúcsból Y csúcsba él vezet.

A fenti fa éleit az alábbi sor írja le: AB AC BD BE CF FG FH Az élek sorrendje nem számít, és mivel a fák irányítatlan fák a karakter párokban sem számít a csúcsokat reprezentáló karakterek sorrendje. A fenti sorral ekvivalens a következő: HF GF CF BD CA BA

A bemenet specifikációja

A bemeneten állományvégjelig tetszőleges számú teszteset érkezik. Minden teszteset két sorból áll. Az első sorban egyetlen karakter található, mely a fa gyökércsúcsát jelöli, ezt egyetlen sor követi, melyben, tetszőlegesen sok karakter pár található, ez a sor leír egy teljes fát.

A kimenet specifikációja

A kimeneten minden tesztesethez tartozóan pontosan egy sor jelenik meg, amelyben egyetlen egész érték a bemeneten szereplő leghosszabb út hosszát adja meg.

Példa bemenet

1. A
2. AB AC CD
3. A
4. AB AC BD BE CF FG FH

Példa kimenet

1. 2
2. 3