require 'set'
loop {
    n = gets.to_i
    break if n == 0
    chain = [nil, Set.new]
    n.times {
	i, j = gets.split.map &:to_i
	ends = set = ((1 << i-1) | (1 << j-1))
	chain[1] << [set, ends]
    }

    l = 2
    loop {
	chain[l] = Set.new
	chain[l/2].each{|s1, e1|
		chain[(l+1)/2].each{|s2, e2|
			i = e1 & e2
			if i > 0 && (i-1) & i == 0 && i == s1 & s2
			    chain[l] << [s1 | s2, e1 ^ e2]
			end
		}
	}
	break if chain[l].empty?
	l += 1
    }
    p l
}