작은 고추들

Afrika paprika! S.V.

정원에서 고된 아침을 보낸 Malnar 씨는 직접 키운 말린 매운 고추로 자신에게 보상하기로 했다.

그는 $n$개의 고추를 가지고 있으며, 고추들은 $n-1$개의 끈으로 연결되어 있다. 어떤 두 고추든 끈을 따라 서로 이어지므로, 이 구조는 트리를 이룬다.

Malnar 씨는 오늘 점심을 세 번 먹는다. 이를 위해 끈 두 개를 잘라 점심마다 하나씩 쓸 작은 컴포넌트 세 개를 만든다.

세 번째 예제의 트리와 최적의 절단 방법이다.

어떤 점심이든 너무 맵지 않아야 하므로, 가장 큰 컴포넌트와 가장 작은 컴포넌트 크기의 차이가 최소가 되도록 끈을 자른다. 그 최소 차이를 구하라.

첫 줄에 고추의 개수 $n$이 주어진다. 고추에는 1부터 $n$까지 번호가 붙어 있다.

이어서 $n-1$개의 줄에 각각 두 정수 $x$, $y$($1 \le x, y \le n$)가 주어진다. 이는 끈으로 직접 연결된 고추의 번호다.

컴포넌트 크기 차이의 최솟값을 출력한다.

첫 번째 예제에서 끈을 자르는 세 가지 방법은 모두 두 개짜리 컴포넌트 하나와 한 개짜리 컴포넌트 두 개를 만든다. 따라서 답은 $2-1=1$이다.

두 번째 예제에서는 1번과 3번, 3번과 5번을 잇는 끈을 자르면 크기가 같은 컴포넌트 세 개를 얻을 수 있다. 따라서 답은 $0$이다.

세 번째 예제의 최적 절단 방법은 문제의 그림에 나와 있다. 컴포넌트 크기는 4, 2, 3이고 답은 $4-2=2$이다.