String-Toys joint-stock company has asked you for help in solving the following problem. They want to manufacture models of connected acyclic graphs made of string.

Each graph consists of vertices and a certain number of edges joining distinct vertices. Each vertex can be joined to many other vertices. A graph is connected and acyclic, if every vertex can be reached from every other vertex by travelling along the edges and furthermore there is a unique way of doing so without turning back.

Graphs' vertices are to be modelled by nodes knotted on bits of string, while edges by the bits of string themselves between the nodes. Each node can be either a knot on a single bit of string or many bits knotted at one point. Due to technical reasons cost of production depends on the number of string bits used in making a model and length of the longest bit. (Each edge has length of 1. Length of string used to making a knot is negligible.)

Task

You are to write a programme that:

• reads from the standard input the description of a connected acyclic graph to be modelled,
• calculates:
  • the minimal number of string bits necessary to making the model,
  • assuming that the number of string bit is minimal, the minimal length of the longest string bit needed to making the model.
• writes the obtained numbers to the standard output.

Input

The first line contains one positive integer n - the number of vertices in the graph, 2 <= n <= 10 000. Vertices are numbered from 1 to n. The following n - 1 lines contain descriptions of edges, one per line. Each of these lines contains a pair of integers a and b separated by a single space, 1 <= a, b <= n, a <> b. Such pair represents an edge joining vertices a and b.

Output

Your programme should write two integers k and l separated by a single space in the first line of the output: k should be the minimal number of string bits required to make the graph's model, while l should be the minimal length of the longest string bit (assuming that k string bits are used).

Example

For the following input data:

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

the correct answer is:

4 2

Print friendly version