시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB116363235.955%

문제

Afrika paprika! – S.V.

After a tiring morning in the garden, Mr. Malnar decided to reward himself with dried hot peppers he grew himself.

He has n peppers, connected with n − 1 pieces of string, so that every two peppers are connected by some series of strings. Formally, they form a tree.

Mr. Malnar will partake in three lunches today. For that purpose, he will cut two strings to get three smaller components, one for each lunch.

The tree from the third example along with the optimal cuts.

It’s bad to make any lunch too spicy, so he will choose the cuts in a way that minimises the difference between the size of the largest and the smallest component. You need to determine the sought minimum difference.

입력

The first line contains an integer n, the number of peppers. The peppers are labeled by integers from 1 to n.

Each of the following n − 1 lines contains two integers x and y (1 ≤ x, y ≤ n) – labels of peppers that are directly connected by a piece of string.

출력

Print the minimum possible difference of component sizes.

서브태스크

번호배점제한
115

3 ≤ n ≤ 200

235

3 ≤ n ≤ 2000

360

3 ≤ n ≤ 200 000

예제 입력 1

4
1 2
2 3
3 4

예제 출력 1

1

예제 입력 2

6
1 2
1 3
3 4
3 5
5 6

예제 출력 2

0

예제 입력 3

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

예제 출력 3

2

힌트

In the first example, each of the possible three ways of cutting the strings yields one component with two peppers and two components with one pepper each. Therefore the answer is 2 − 1 = 1.

In the second example, it’s possible to get three components of the same size by cutting the string that connects peppers 1 and 3, and also 3 and 5, so the answer is 0.

Optimal cuts for the thirds example are shown on the figure in the statement. The sizes of the components are 4, 2 and 3, and the answer is 4 − 2 = 2.

채점 및 기타 정보

  • 예제는 채점하지 않는다.