## DWITE '11 R2 #4 - Bear Trees

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem types
##### 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