Polish version    English version  
  History of OI -> XI OI 2003/2004 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
Schedule
Problems
Stage III - results
Stage II - results
Stage I - results
Stage II
Stage III
Rules
For contestants
Helpful resources
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
XI Olympiad in Informatics 2003/2004

Zadanie: szn

Strings

I stage competition  
Source file: szn.xxx (xxx=pas,c,cpp)
Memory limit: 32 MB

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

Example




Print friendly version