In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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:
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:
Task author: Marcin Kubica.