Problem Description

The company $\text{String-Toys joint-stock}$ needs your help to solve a problem.

They want to build a connected graph model without cycles. Each graph consists of some vertices and a fixed number of edges. Each vertex can be connected to many other vertices. A graph that is connected and has no cycles can be made from several strings. A string is a path connecting two vertices in the graph.

Due to technical reasons, different strings are not allowed to overlap. You must ensure that every edge in the graph is covered by exactly one string.

The cost of building such a model depends on how many strings are used and the length of the longest string (each edge has length $1$).

Now you are given the graph. Please write a program to find the minimum number of strings needed, and under this minimum, the smallest possible length of the longest string.

Input Format

The first line contains a single integer $n$, the total number of vertices. The vertices are numbered from $1$ to $n$.

The next $n - 1$ lines describe the edges. Each line contains two integers $a$ and $b$, meaning there is an edge between vertex $a$ and vertex $b$.

Output Format

Output two integers: the minimum number of strings, and under this minimum, the minimum possible length of the longest string.

9
7 8
4 5
5 6
1 2
3 2
9 8
2 5
5 8

4 2

Hint

For $100$ % of the testdata: $2 \le n \le 10000,1 \le a,b \le n$.

Explanation of the sample:

Translated by ChatGPT 5