그랜드 센트럴 스테이션

당신이 사는 도시에 새로운 교통망 PlusRail이 막 완공되었다. 역이 n개 있고, 임의의 두 역 사이를 오가는 방법은 정확히 하나뿐이다. 역과 역을 직접 잇는 연결이 n − 1개뿐이기 때문이다. 즉, 이 교통망은 트리를 이룬다.

당신은 각 역에 붙일 안내판을 만들어야 한다. 안내판은 승객이 교통망의 어디에 있는지를 보여 주며, 가운데에 있는 새빨간 역을 가리키는 큰 화살표가 그려져 있다.

그림 G.1: 예제 입력 1을 나타낸 그림으로, 두 디자인이 네 번 재사용되며 역 이름표가 서로 다른 위치에 쓰인다.

교통망을 그린 그림이 상당히 조잡하기 때문에, 같은 안내판을 여러 역에서 쓰고 역 이름표만 다르게 적는 것이 가능하다.

교통망 전체의 안내판을 만들려면 서로 다른 디자인이 최소 몇 개 필요한가?

• 첫째 줄에 역의 수 n이 주어진다. (1 ≤ n ≤ 3 × 105)
• 다음 n − 1개 줄에 두 역을 잇는 직접 경로가 있음을 나타내는 서로 다른 두 역 번호 a, b가 주어진다. (1 ≤ a, b ≤ n)

임의의 역에 대해, 그 역이 가운데에 오도록 다시 이름표를 붙일 수 있는 디자인이 적어도 하나 존재하게 만드는 최소 디자인 수를 출력한다.