보석

보석 완구 회사에서 다음 문제를 풀어 달라고 요청했습니다.

연결되어 있고 사이클이 없는 그래프, 즉 트리가 주어집니다. 트리는 정점들이 간선으로 연결되어 있어 어느 정점에서든 다른 모든 정점으로 갈 수 있으며, 사이클이 없는 그래프입니다.

이 회사는 이러한 트리 모양의 장신구 모형을 만들려고 합니다. 각 정점은 보석으로, 각 간선은 금실로 만들어집니다. 서로 인접한 두 정점은 서로 다른 종류의 보석이어야 합니다. 모든 양의 정수 $p$에 대해 가격이 $p$인 보석이 정확히 한 종류 있습니다.

모형을 만드는 데 필요한 보석 가격의 최소 합을 구하세요.

첫째 줄에 정점의 개수 $N$ ($1 \le N \le 10\,000$)이 주어집니다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있습니다.

다음 $N-1$개의 줄에는 각각 두 정수 $A$와 $B$ ($1 \le A, B \le N$, $A \ne B$)가 주어지며, 이는 정점 $A$와 $B$를 잇는 간선을 나타냅니다.

모형을 만드는 데 필요한 보석 가격의 최소 합을 정수 하나로 출력합니다.