전력 감시 시스템

전력 계통은 전기 노드와 송전선으로 이루어진다. 전기 노드는 송전선, 부하, 발전기가 연결되는 변전소 모선이다. 송전선은 두 전기 노드를 잇는다. 전력 회사는 전력 계통을 정상적으로 운영하려고 부하의 전압 크기, 발전기의 기계 위상각 같은 상태 변수를 계속 감시한다. 회사는 선택한 전기 노드에 PMU를 설치해 이 변수(전압과 위상각)를 감시한다.

위상 측정 장치(PMU)는 설치된 전기 노드의 상태 변수와, 그 노드에 연결된 송전선 및 송전선 반대편 끝의 노드 상태 변수를 측정한다. 이 노드와 송전선을 감시 대상이라고 부른다. 나머지 노드와 송전선은 다음 규칙에 따라 재귀적으로 감시 대상이 된다.

1. 감시 대상인 송전선에 연결된 노드는 감시 대상이다.
2. 감시 대상인 두 노드를 잇는 송전선은 감시 대상이다.
3. 노드에 연결된 송전선이 총 $k$개($k > 1$)이고 그중 $k-1$개가 감시 대상이면, 그 노드에 연결된 $k$개의 송전선은 모두 감시 대상이다.

그림 3(a)는 전체 시스템을 감시하는 배치이고, 그림 3(b)는 감시하지 못하는 배치이다.

그림 3(a)에서 PMU1은 노드 1, 2, 3, 4와 송전선 a, b, c를, PMU2는 노드 6, 8, 9, 10과 송전선 g, h, i를 감시한다. 노드 4와 6이 감시 대상이므로 규칙 2에 따라 송전선 e도 감시 대상이 된다. 송전선 d와 f는 규칙 3에 따라 각각 노드 4와 6에서 마지막으로 남은 송전선이므로 감시 대상이 된다. 노드 5와 7은 규칙 1에 따라 감시 대상이 된다.

리치 시티의 전력 계통은 트리 구조(루프가 없는 구조)이다. 전체 시스템을 감시하는 데 필요한 PMU의 최소 개수를 구하는 프로그램을 작성하라.

첫째 줄에 전기 노드의 개수 $n$($2 \le n \le 100000$)이 주어진다. 이어서 $n-1$개의 줄에 송전선으로 인접한 두 전기 노드의 번호가 공백으로 구분된 정수 두 개씩 주어진다.

전체 시스템을 감시할 수 있는 PMU의 최소 개수를 출력한다.

노드는 $n$개이며, $2 \le n \le 100000$이다. 각 노드는 1부터 $n$까지의 서로 다른 번호를 가지며, 번호는 루트 노드에서 시작한 너비 우선 탐색 순서로 매겨져 있다.