체크포인트

문제

$1$번부터 $N$번까지 번호가 붙은 정점으로 이루어진 트리가 있다. 이 트리의 루트는 $1$번 정점이다. 소원이는 처음에 $1$번 정점에 있으며, 모든 정점을 적어도 한 번 방문하려고 한다.

소원이는 다음 세 가지 행동을 원하는 만큼 할 수 있다.

• 이동: 현재 정점의 자식 정점으로 간선을 따라 이동한다. 간선 하나를 지날 때마다 비용 $1$이 들며, 부모 정점으로는 이동할 수 없다.
• 와드 설치: 현재 정점에 와드를 설치한다. 비용은 들지 않으며, 이미 설치된 와드가 있다면 사라지고 새 와드만 남는다.
• 순간이동: 와드가 설치된 정점으로 순간이동한다. 비용은 들지 않으며, 순간이동한 뒤에도 와드는 사라지지 않는다. 와드가 설치되어 있지 않으면 순간이동할 수 없다.

처음에는 와드가 설치되어 있지 않다. 소원이는 시작 위치인 $1$번 정점에도 와드를 설치할 수 있다.

이미 방문한 정점을 다시 방문해도 되며, 순간이동으로 도착한 정점도 방문한 것으로 센다.

소원이가 모든 정점을 적어도 한 번 방문하는 데 필요한 최소 비용을 구하여라.

입력

첫째 줄에 정점의 수 $N$이 주어진다. $(1 \le N \le 100,000)$

다음 $N-1$개의 줄에 간선으로 연결된 두 정점의 번호 $u$, $v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N; u \ne v)$

주어지는 간선은 방향이 없으며, 전체 그래프는 트리이다. 부모와 자식 관계는 $1$번 정점을 루트로 하여 정한다.

출력

모든 정점을 적어도 한 번 방문하는 데 필요한 최소 비용을 출력한다.

예제 1

7
1 2
1 3
2 4
2 5
3 6
3 7

출력 1

7

힌트

다음과 같이 모든 정점을 방문할 수 있다.

1. $1$번 정점에 와드를 설치한다.
2. $1 \to 3 \to 6$으로 이동한 뒤 $1$번 정점으로 순간이동한다. 이동 비용은 $2$이다.
3. $1 \to 3 \to 7$로 이동한 뒤 $1$번 정점으로 순간이동한다. 이동 비용은 $2$이다.
4. $1 \to 2$로 이동한 뒤 $2$번 정점에 와드를 설치한다. 이동 비용은 $1$이며, $1$번 정점의 와드는 사라진다.
5. $2 \to 4$로 이동한 뒤 $2$번 정점으로 순간이동한다. 이동 비용은 $1$이다.
6. $2 \to 5$로 이동한다. 이동 비용은 $1$이다.

총비용은 $2+2+1+1+1=7$이며, 이보다 적은 비용으로 모든 정점을 방문할 수는 없다.