Problem Description

OItown is surrounded by n small villages. Villages are connected by roads, with each road linking two villages. Due to the limited wealth of these villages, the roads were built to just connect all the villages, meaning there is only one unique way to travel from any village to another via roads. Consequently, sometimes two close villages require a long journey. Therefore, the villagers hope to establish public transport routes on these roads to facilitate travel.

The bus company has adopted this suggestion. However, they stipulate that the bus routes must meet the following conditions:

1. The start and end points of each bus route are within villages, and the routes follow the roads.
2. Each road must be covered by a bus route, so villagers only need to change buses for travel.
3. Each road is covered by only one bus route and covered exactly once, as the bus company considers multiple coverage cost-inefficient.
4. The total number of bus routes should be minimized for ease of management.

For example, if there are 6 villages connected by 5 roads as shown:

Then these 3 bus routes meet the conditions: 1-2-3, 2-4, 5-4-6.

However, villagers find "bus transfers" inconvenient and hope that the maximum number of transfers required to travel from one village to another is minimized. For instance, in the above route arrangement, traveling from village 1 to village 6 requires 2 transfers, which is the maximum.

On the other hand, the bus company believes that the longer a bus route is, the more passengers are affected if a bus breaks down. Therefore, they want the longest route to be as short as possible, meaning it passes through fewer villages.

Your task is to design these bus routes, considering both factors. Thus, you need to calculate: (1) the minimum possible value of the maximum number of transfers, and (2) the minimum possible number of villages passed through by the longest route.

Input Format

The first line of the input data is an integer n, representing the number of villages.

Each subsequent line contains two integers x and y, describing a road, indicating that there is a road between village x and village y.

The input file guarantees that each road is described only once.

Output Format

The output file contains three lines:

The first line is an integer representing the number of bus routes in the arrangement.

The second line is an integer representing the minimum possible value of the maximum number of transfers.

The third line is an integer representing the minimum possible number of villages passed through by the longest route.

Sample Input and Output

Sample Input #1

6
1 2
2 3
4 5
5 6
2 5

Sample Output #1

3
2
3

Sample Input #2

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

Sample Output #2

6
2
3

Notes

If your first line of output matches the standard answer, you can earn 2 points.

If your second line of output matches the standard answer, you can earn 4 points.

If your third line of output matches the standard answer, you can earn 4 points.

For 70% of the data: n <= 300
For 100% of the data: n < $10^5$

见题面 Input 部分

见题面 Output 部分