type graph = Graph of int * bool array array

let create_graph strings =
  let n = List.length strings in
  let graph = Array.make_matrix (n + 1) (n + 1) false in
  List.iter
    (fun (i, j) ->
     graph.(i).(j) <- true;
     graph.(j).(i) <- true)
    strings;
  Graph (n, graph)

let iota ?(init=0) ?(step=1) n =
  let rec iota i n acc =
    if n = 0 then List.rev acc
    else iota (i + step) (pred n) (i :: acc) in
  iota init n []

let neighbors (Graph (n, graph)) i =
  let neighbors = ref [] in
  for j = n downto 1 do
    if graph.(i).(j) && i <> j then
      neighbors := j :: !neighbors
  done;
  !neighbors

module IntSet = Set.Make (
                    struct
                      type t = int
                      let compare (x : int) y = compare x y
                    end
                  )

let longest_chain_length (Graph (n, graph) as g) =
  let rec longest_chain_length i visited =
    let visited = IntSet.add i visited in
    let neighbors =
      List.filter (fun j -> not @@ IntSet.mem j visited) (neighbors g i) in
    if neighbors = [] then 0
    else
      let subchain_lengths =
        List.map (fun j -> longest_chain_length j visited) neighbors in
      1 + List.fold_left max 0 subchain_lengths in
  1 + (List.fold_left max 0
       @@ List.map (fun i -> longest_chain_length i IntSet.empty)
                   (iota ~init:1 n))

let solve strings = longest_chain_length @@ create_graph strings

let read_lines n =
  let rec read_lines n acc =
    if n = 0 then List.rev acc
    else read_lines (pred n) ((read_line ()) :: acc) in
  read_lines n []

let rec loop () =
  let n = int_of_string @@ read_line () in
  if n = 0 then ()
  else
    let input = List.map
                  (fun line -> Scanf.sscanf line "%d %d" (fun i j -> (i, j)))
                  (read_lines n) in
    print_endline @@ string_of_int @@ solve input;
    loop ()

let () = loop ()