Path Decomposition of a Tree

A joint‐stock company, String-Toys, has a tree (i.e. a connected acyclic graph) with n vertices and n − 1 edges. They wish to partition the edges of this tree into simple paths (called lines) such that each edge is covered by exactly one line and any two lines do not share an overlapping edge. Each edge has unit length. The cost of a decomposition depends on two factors: the number of lines used and the length of the longest line (in which the length is simply the number of edges in that path).

It can be shown that the minimum number of lines required is [ \left\lceil \frac{L}{2} \right\rceil, ] where L is the number of leaves (vertices with degree 1) in the tree. Among all decompositions achieving this minimum count, the company wishes to choose one in which the length of the longest line is as small as possible.

Your task is:

• Given the tree, first compute the minimum number of lines as ceil(L/2).
• Then, among all valid decompositions that use exactly ceil(L/2) lines, determine the smallest possible value of the maximum line length. (A line is defined as a simple path in the tree and its length is the number of edges it contains; every edge in the tree is covered exactly once.)

Input Format:
The first line contains an integer n (the number of vertices). Each of the following n − 1 lines contains two integers u and v (1-indexed) indicating an edge between vertices u and v.

Output Format:
Output two integers separated by a space: the first is the minimum number of lines (which equals \(\lceil L/2 \rceil\)) and the second is the minimum possible value of the maximum line length in such an optimal decomposition.

Note: It is guaranteed that the input graph is a tree. Each edge length is 1.

inputFormat

The input begins with a single integer n (2 ≤ n ≤ 10⁵, though typical test cases will be smaller) indicating the number of vertices. Then follow n − 1 lines, each containing two integers u and v (1-indexed) that denote an edge between vertices u and v.

outputFormat

Output two space‐separated integers. The first integer is the minimum number of lines required to partition the tree (which equals (\lceil L/2 \rceil), where L is the number of leaves). The second integer is the minimum possible value of the maximum line length among all decompositions that use this number of lines.

sample

4
1 2
2 3
3 4

1 3