Tree Modification: Minimizing and Maximizing Diameter

Given an undirected tree with all edge weights equal to \(1\), you are allowed to perform the following operation exactly once: remove one edge and add one new edge such that the graph remains a tree. The diameter of a tree is defined as the maximum distance between any two nodes (i.e. the length of the longest simple path). With the operation, different new trees can be obtained. Your task is to compute the minimum and maximum possible diameters over all valid operations.

More formally, suppose an edge \(e\) is removed which splits the tree into two components \(T_1\) and \(T_2\). Let \(d_1\) and \(d_2\) be the diameters of \(T_1\) and \(T_2\), respectively. Also, let \(r_1=\lceil d_1/2\rceil\) and \(r_2=\lceil d_2/2\rceil\) be the radii. By connecting a vertex from \(T_1\) and a vertex from \(T_2\) with a new edge, the resulting tree's diameter is given by

[ D = \max\Bigl( d_1,; d_2,; r_1 + r_2 + 1 \Bigr). ]

This is the minimum possible diameter for that particular removal (obtained by optimally choosing the two vertices to connect). On the other hand, by choosing the two farthest endpoints in \(T_1\) and \(T_2\) respectively, one may achieve a diameter of

[ D = d_1 + d_2 + 1. ]

Your task is to output two numbers: the minimum achievable diameter over all valid operations, and the maximum achievable diameter over all valid operations.

inputFormat

The first line contains an integer \(n\) (\(n\ge2\)), the number of nodes in the tree.

Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) (1-based indices) indicating that there is an edge between nodes \(u\) and \(v\).

outputFormat

Output two integers separated by a space: the minimum achievable diameter and the maximum achievable diameter, respectively.

sample

4
1 2
1 3
1 4

2 3