Polish version    English version  
  History of OI -> XI OI 2003/2004 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
Rules
For contestants
Helpful resources
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
XI Olympiad in Informatics 2003/2004

Task: jas

Cave

II stage competition  
Source file: jas.xxx (xxx=pas,c,cpp)
Memory limit: 16 MB

There is a cave in Byteotia. It consists of n chambers and corridors connecting them. The corridors are arranged in such way, that there is a unique path between each pair of chambers. In one of these chambers Hansel has hidden a treasure, but he won't tell which one it is. Gretel desires to know it. So she asks Hansel about various chambers. When she guesses right Hansel tells her she is right, and when she guesses wrong he tells her which way from this chamber leads to the treasure.

Task

Write a programme that:

  • reads from the standard input the description of the cave,
  • finds the minimal number of questions Gretel has to ask in the worst case to learn in which chamber the treasure is hidden,
  • writes the result to the standard output.

Input

In the first line of the standard input there is one positive integer n, 1<= n <= 50,000. It is the number of chambers in the cave. The chambers are numbered from 1 to n. In the following n-1 lines the corridors linking the chambers are described, one per line. Each of these lines contains a pair of distinct positive integers a and b (1<= a,b <= n), separated by a single space. It indicates that there is a corridor between chambers a and b.

Output

Your programme should write one integer in the standard output, the minimal number of questions Gretel has to ask in the worst case (i.e. we assume Gretel asks the questions in the best possible way, but the treasure is hidden in the chamber that requires the largest number of questions).

Example

For the following input data:


5
1 2
2 3
4 3
5 3

the correct answer is:

2



Print friendly version