바이러스

컴퓨터 바이러스가 이진 트리 모양의 네트워크로 퍼진다. 감염과 방어는 다음 과정을 따른다.

1. 시각 0에 바이러스가 루트를 감염시킨다.
2. 그 뒤 각 시각마다 두 가지 일이 순서대로 일어난다. 먼저 감염되지 않은 노드 하나를 백신으로 방어할 수 있다. 그다음 바이러스가 감염된 모든 노드에서 방어되지 않은 자식 노드 전체로 퍼진다. 한 번 감염되거나 방어된 노드의 상태는 과정이 끝날 때까지 그대로 남는다.
3. 바이러스가 더 퍼질 수 없으면 과정이 끝난다.

한 시각에 방어할 수 있는 노드는 최대 하나이고, 아무 노드도 방어하지 않아도 된다.

목표는 과정이 끝났을 때 감염된 노드의 수를 최소로 만드는 것이다.

위 그림의 네트워크에서 노드 1의 자식은 2와 3, 노드 2의 자식은 4 하나, 노드 3의 자식은 5와 6이다. 시각 0에 바이러스가 루트인 노드 1을 감염시킨다. 시각 1에 노드 3을 방어하면 바이러스는 노드 2를 감염시킨다. 이어서 시각 2에 노드 4를 방어하면 바이러스가 더 퍼질 수 없고, 감염된 노드는 2개다. 시각 1에 노드 3 대신 노드 2를 방어하면 바이러스가 노드 3을 감염시키는데, 이때도 감염된 노드는 2개보다 적어지지 않는다. 따라서 이 네트워크의 최솟값은 2다.

이진 트리로 주어진 네트워크에서 감염된 노드 수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 노드의 개수 $n$ ($1 \le n < 2^{20}$)이 주어진다. 이어지는 $n$개 줄 중 $i$번째 줄에는 노드 $i$의 왼쪽 자식과 오른쪽 자식을 나타내는 정수 두 개가 주어진다. 노드에는 1번부터 $n$번까지 번호가 붙어 있고, 루트는 노드 1이며, 자식이 없으면 0으로 나타낸다.

감염된 노드 수의 최솟값을 한 줄에 출력한다.