DWITE, November 2011, Problem 4
Gary is a bear. He lives in a system of caves, consisting of caverns, numbered from through . These caverns are connected by bidirectional tunnels, such that there is exactly one path between each pair of tunnels. (You might also know this kind of structure as a "tree", so you'll know that there are exactly tunnels.)
Gary would like to explore this system of caves, using the following method:
- Put cavern (his home) on a "to explore" list.
- Choose one cavern from the list.
- Remove from the list.
- Explore : Add all caverns adjacent to that have never been on the list.
- Repeat steps to while the list contains at least one cavern.
There are many ways to explore a system of caves. However, bears are forgetful. You would like to find a way to explore the cave such that the maximum length of the list is minimized. For example, given the following tree:
Here is one possible way to explore the tree, where the maximum length of the list is :
- Explore , list =
- Explore , list =
- Explore , list =
- Explore , list =
- Explore , list =
- Explore , list =
- Explore , list =
However, exploring in a different order, Gary can make it such that he never has to remember more than elements; indeed, it is easy to see that is optimal. Gary has retained you to find this minimum list length, given a system of caves.
Input Specification
The input will contain 5 test cases. Each test case will begin with one line, containing the number of caverns . lines will follow, each consisting of two distinct space-separated integers and , denoting a tunnel between caverns and . Of course, no tunnel will be described more than once, and .
Output Specification
The output will contain 5 lines of output, the minimum list length for each cave system.
Sample Input
7
0 1
0 2
0 3
2 4
2 5
3 6
4
0 1
1 2
2 3
Sample Output
3
1
Problem Resource: DWITE
Comments
Since the original data were weak, an additional test case was added, and all submissions were rejudged.
The additional test case has been modified to the input specifications, and all submissions were rejudged.