import Control.Monad (replicateM)
import Data.Maybe (fromJust)
import Data.List (sort,group)
import qualified Data.Map.Strict as Map
import qualified Data.Set as Set

main = do
    n <- readLn
    if n == 0 then return () else do
        ps <- replicateM n (getLine >>= return . (\[a,b]->(a,b)) . map read . words)
        print $ maxLength $ strings ps
        main

type Strings = Map.Map Int [Int]

strings :: [(Int,Int)] -> Strings
strings ps = foldr (uncurry Map.insert) Map.empty [(i,otherside i)|i<-rings]
    where
    otherside a = [b|(a',b)<-ps,a'==a] ++ [b|(b,a')<-ps,a'==a]
    rings = map head $ group $ sort $ (map fst ps ++ map snd ps)

maxLength strings = maxLength' [(i,Set.singleton i)|i<-Map.keys strings] 1
    where
    maxLength' []     n = n-1
    maxLength' chains n = maxLength' (chains >>= augment) (n+1)

    augment :: (Int,Set.Set Int) -> [(Int,Set.Set Int)]
    augment (end,chain) = map (\r -> (r, Set.insert r chain)) newRings
        where
        newRings = filter (`Set.notMember` chain)
                    (fromJust $ Map.lookup end strings)