여행

플랫랜드에는 $n$개의 도시가 있고, 일부 도시끼리는 양방향 도로로 연결되어 있다. 도로망은 어느 도시에서 출발하든 다른 도시로 가는 방법이 정확히 하나뿐인 구조이다. 최근 플랫랜드의 왕은 모든 도시를 정확히 한 번씩 방문하고 수도로 돌아오는 여행을 하고 싶어 한다. 왕은 어떤 도로도 두 번 이상 지나가지 않기를 원한다.

교통부 장관은 왕에게 이 여행이 불가능하다고 설명했다. 플랫랜드의 도로망에는 사이클이 없기 때문이다. 그러나 왕은 이 여행을 반드시 하겠다고 고집했다. 그렇다면 새 도로를 건설하는 수밖에 없다.

도로 건설 장관을 도와, 왕이 여행할 수 있도록 건설해야 하는 도로의 최소 개수를 구하라.

첫째 줄에 플랫랜드의 도시 개수 $n$이 주어진다 ($3 \le n \le 100\,000$). 다음 $n-1$개 줄에는 도로가 각각 두 정수로 주어지며, 이 두 수는 도로가 연결하는 도시의 번호이다. 도시는 1부터 $n$까지 번호가 매겨져 있다.

왕이 여행할 수 있도록 건설해야 하는 도로의 최소 개수를 한 줄에 출력한다.

예시에서는 예를 들어 도로 3-4와 4-5를 건설할 수 있다. 그러면 왕은 경로 1-2-3-4-5-1을 따라 여행할 수 있다.