Description

There are $n$ small villages around OItown. There are roads between villages, and each road connects two villages. Because these villages are not wealthy, when the roads were built, they were built just enough to make all villages connected. That is, for any two villages, there is a unique way to walk from one to the other along the roads. Therefore, sometimes two villages that are very close still require a long walk along the roads. So the villagers hope to open public transport routes on these roads to make travel more convenient.

The bus operating company accepted this suggestion. At the same time, the company requires that the bus routes must satisfy the following conditions:

1. The start and end points of each bus route are in villages, and the bus runs along the roads.
2. Every road must be covered by some bus route, so that villagers only need to switch to taking buses.
3. Each road is covered by exactly one bus route, and is covered only once. Otherwise, the company thinks it is not cost-effective.
4. The total number of bus routes should be as small as possible, to make management easier.

For example, if the $5$ roads among $6$ villages are like this:

Then the following $3$ bus routes can satisfy the conditions above: $1-2-3$, $2-4$, $5-4-6$.

However, the residents naturally think that “bus transfers” are inconvenient, so they hope that the maximum number of transfers needed when traveling from one village to another is as small as possible. For example, in the route arrangement above, going from village $1$ to village $6$ requires $2$ transfers, which is the maximum number of transfers.

On the other hand, the bus company believes that a longer bus route means that if a bus breaks down, more passengers will be affected and delayed. Therefore, the company hopes that the longest route is as short as possible. “Short” means it passes through fewer villages.

Now the task of designing the bus routes is given to you, a contestant of SHTSC. You must consider both factors above, so you need to compute: (1) the minimum possible value of the maximum number of transfers. (2) the minimum possible value of the number of villages passed through by the longest route.

Input Format

The first line of the input contains an integer $n$, the number of villages.

Each of the following lines contains two integers $x$ and $y$, describing a road, meaning there is a road between villages $x$ and $y$.

The input guarantees that each road is described only once.

Output Format

The output has three lines:

The first line contains an integer, the number of routes in the bus route arrangement.

The second line contains an integer, the minimum possible value of the maximum number of transfers.

The third line contains an integer, the minimum possible value of the number of villages passed through by the longest route.

6
1 2
2 3
4 5
5 6
2 5

3
2
3

12
1 2
2 3
3 4
4 5
5 6
6 7
2 8
3 9
4 10
5 11
6 12

6
2
3

Hint

If the first line of your output is the same as the standard answer, you can get $2$ points.

If the second line of your output is the same as the standard answer, you can get $4$ points.

If the third line of your output is the same as the standard answer, you can get $4$ points.

Constraints:

For $70\%$ of the testdata: $n \le 300$. For $100\%$ of the testdata: $n \le 10^5$.

Translated by ChatGPT 5