Optimal Bus Lines Partition

OItown is surrounded by n villages connected by exactly n-1 roads so that there is exactly one simple path between any two villages (i.e. the road network forms a tree). The bus company must design bus routes subject to the following conditions:

1. The start and end of each bus route are villages; the bus travels along the roads.
2. Every road must be covered by some bus route (so that villagers can travel entirely by bus).
3. Each road is covered by exactly one bus route (i.e. no road is served twice).
4. The total number of bus routes must be as small as possible.

It can be shown that the minimum number of bus routes needed is odd(v)/2, where odd(v) is the number of villages having an odd degree in the tree.

However, the villagers dislike transfers. When one journeys by bus from one village to another, each time one changes from one bus route to a different one counts as a transfer. They want the maximum number of transfers required (over all pairs of villages) to be as small as possible.

On the other hand, the bus company wishes that no single bus route is too long (a route’s length is measured by the number of villages it passes through) so that a breakdown does not affect too many passengers. Hence, subject to minimizing the maximum transfers needed, the company wants the longest bus route (i.e. the maximum number of villages on any bus route) to be as short as possible.

Your task is: given the tree, compute two numbers:

1. The minimum possible value of the maximum number of transfers (i.e. bus-route changes) needed between any two villages under any valid bus route scheme that uses the minimum number of routes.
2. Subject to (1), the minimum possible value of the length (in number of villages) of the longest bus route.

Note: A journey’s bus-route count is the number of bus routes used along the unique path between two villages; the number of transfers equals that number minus one. For example, consider the following tree of 6 villages with 5 roads:

Edges: 1–2, 2–3, 2–4, 4–5, 4–6. One valid bus route scheme is:

• Route A: 1–2–3
• Route B: 2–4
• Route C: 5–4–6

In this scheme, the journey from village 1 to village 6 uses routes A, B and C (thus 2 transfers) – and 2 is the maximum number of transfers among all pairs. Also, the longest route in this scheme passes through 3 villages. It turns out that these values are optimal.

Input/Output Format described below.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵) representing the number of villages. The following n–1 lines each contain two integers u and v (1 ≤ u,v ≤ n), indicating a road connecting villages u and v.

The input is guaranteed to form a tree.

outputFormat

Output two integers separated by a space:

• The minimum possible maximum number of transfers (i.e. bus-route changes) needed between any two villages.
• The minimum possible length (in number of villages) of the longest bus route under a scheme achieving (1).

Note: If a journey is completed on a single bus route, the transfer count is 0.

sample

6
1 2
2 3
2 4
4 5
4 6

2 3