573 . Cave
Description
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.
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 Format
There are multiple test cases in the input file. For each test case:
In the first line of the standard input there is one positive integer n, 1<= n<= 50000. 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 Format
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).
There is no need to print any blank lines between test cases.
Sample Input 1
5 1 2 2 3 4 3 5 3 7 1 2 2 3 3 4 4 5 5 6 6 7
Sample Output 1
2 2
Hints
Problem Source
Migrated from old NTUJ.
POI 15th Stage III
Subtasks
| No. | Testdata Range | Score |
|---|