27950번 - 가지농장 수확하기

문제

새롭고 놀라운 가지를 교배하는 가지 연구원 민규는 여러가지 가지를 교배하여 슈퍼 가지를 만들었다! 민규는 즉시 슈퍼 가지를 기르는 농장을 만들었고, 슈퍼 가지들은 열심히 자라서 수확할 시간이 되었다.

민규의 농장은 1ドル$번에서 $N$번까지 번호가 붙은 $N$개의 토지와 그 토지들을 잇는 길이 1ドル$의 도로 $N-1$개로 이루어져 있다. 어느 토지에서든 도로를 통해서 다른 모든 토지로 갈 수 있고, 오직 하나의 토지와 도로로 직접 연결되어 있는 비옥한 토지에만 민규가 슈퍼 가지를 심었다. 단, 1ドル$번 토지에는 창고가 있기 때문에 슈퍼 가지를 절대 심지 않는다.

예제 1ドル$의 농장. 원형이 토지, 녹색이 창고, 보라색이 가지를 심은 토지이다.

민규는 현재 1ドル$번 토지에 있고, 민규는 민규가 있는 토지와 연결되어 있는 도로 중 하나를 통해서 움직일 수 있다. 민규가 슈퍼 가지가 심어져 있는 토지에 도착하게 되면 슈퍼 가지를 수확할 수 있고, 수확한 슈퍼 가지를 들고 다시 움직이게 된다. 하지만, 슈퍼 가지들을 안전하게 보관하기 위해 민규는 한번에 슈퍼 가지를 최대 3ドル$개씩만 들고 움직일 수 있다. 민규가 창고가 위치해 있는 1ドル$번 토지에 도착하게 된다면, 현재 민규가 들고 있는 슈퍼 가지를 모두 저장할 수 있다. 즉, 민규는 다시 3ドル$개의 슈퍼 가지를 들 수 있게 된다.

민규는 농장에서 자란 모든 슈퍼 가지를 최대한 빨리 수확해 창고에 저장하려고 한다. 민규가 모든 슈퍼 가지를 수확하여 창고에 저장하려 할 때 움직여야 하는 총 거리의 최솟값을 구하자.

입력

첫째 줄에 농장의 토지 개수 $N$이 주어진다. $(2 \le N \le 10,000円)$

둘째 줄부터 $N - 1$개의 줄에 걸쳐 양의 정수 $a$와 $b$가 주어진다. 이는 $a$번 토지와 $b$번 토지를 연결하는 길이 1ドル$의 도로가 존재한다는 정보를 나타낸다. $(1 \le a,b \le N;$ $a \ne b)$ 두 토지를 연결하는 도로는 최대 하나뿐이다.

출력

첫째 줄에 민규가 모든 가지를 수확해 창고에 저장하기 위해 움직여야 하는 거리의 최솟값을 출력한다.

제한

힌트