0 人解决，0 人已尝试。
0 份提交通过，共有 0 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 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.
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.
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).
9 7 8 4 5 5 6 1 2 3 2 9 8 2 5 5 8
4 2 hint:
0 人解决，0 人已尝试。
0 份提交通过，共有 0 份提交。
9.9 EMB 奖励。