In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

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.)

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 - the number of vertices in the graph, . Vertices are numbered from to . The following lines contain descriptions of edges, one per line. Each of these lines contains a pair of integers and separated by a single space, , . Such pair represents an edge joining vertices and .

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

For the input data:

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

the correct result is:

4 2

*Task author: Marcin Kubica.*