우편배달부

Johnny는 방금 우체부가 되었다. 회사에 들어온 지 얼마 되지 않은 그는 새 동네에 긴급 우편을 배달하는 가장 힘든 업무를 맡았다. 배달 기한은 정확히 1시간 뒤이다. 우편회사는 고객 친화적인 새 규칙도 도입했다. 기한이 지나서 배달된 편지마다, 늦어진 1시간당 $1$ bythaler의 보상금을 회사가 지급한다.

동네에는 $n$채의 집이 있고, 1번부터 $n$번까지 번호가 붙어 있다. Johnny는 집마다 편지를 한 통씩 배달해야 한다. 집들은 $n-1$개의 양방향 도로로 연결되어 있어, 어느 집에서든 도로를 따라 다른 모든 집으로 갈 수 있다.

Johnny는 편지를 최대한 빨리 배달해야 한다. 회사 운전 규정에 따라 회사 차가 그가 고른 집 한 곳까지 그를 데려다주고, 그 뒤부터는 Johnny가 걸어서 이동한다. 차로 이동하는 데는 정확히 1시간이 걸리므로, 그 집의 편지 한 통만 제시간에 배달된다. 도로 하나를 걷는 데도 정확히 1시간이 걸린다. 우편함에 편지를 넣는 시간은 무시한다. Johnny는 모든 편지를 배달해야 한다.

Johnny는 제시간에 모든 배달을 끝내는 것이 불가능하다는 것을 알고 있지만, 그래도 우편회사가 지급하는 보상금 합계를 최소로 줄이고 싶어 한다. 집의 수와 도로 정보를 입력받아 기한을 넘긴 배달의 보상금 최솟값을 구해 출력하는 프로그램을 작성하라.

첫 줄에 집의 수를 나타내는 정수 $n$ ($1 \le n \le 1\,000\,000$)이 주어진다. 이어지는 $n-1$개의 줄에는 공백으로 구분된 두 정수 $a$와 $b$ ($1 \le a,b \le n$)가 한 줄에 하나씩 주어지며, 이는 $a$번 집과 $b$번 집이 도로로 직접 연결되어 있음을 뜻한다.

보상금의 최솟값을 bythaler 단위로 출력한다.

Johnny는 1번 집에 내려 편지를 제시간에 배달하므로 보상금은 $0$이다. 그다음 2번 집까지 걸어가 배달하면 보상금은 $1$, 3번 집까지 걸어가 배달하면 $2$가 된다. 이후 2번 집으로 돌아와 4번 집까지 걸어가 배달하면 보상금은 $4$, 다시 2번 집으로 돌아와 5번 집까지 걸어가 마지막 편지를 배달하면 보상금은 $6$이다.