1 人解决，2 人已尝试。
2 份提交通过，共有 3 份提交。
9.5 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 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.
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.
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).
5 1 2 2 3 4 3 5 3
2 hint:
1 人解决，2 人已尝试。
2 份提交通过，共有 3 份提交。
9.5 EMB 奖励。