Virus

Time limit2sMemory limit512 MB

Summary

Given a binary tree, find the minimum number of nodes that end up infected when one node may be protected each round.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, Greedy, DFS
Solved: No attempts yet

Problem

A computer virus spreads through a network shaped like a binary tree. Nodes get infected or protected in this process:

At time 0 the virus infects the root.
At every later time step two things happen, in this order. First, one uninfected node can be protected with a vaccine. Then the virus spreads from every infected node to all of its unprotected children. A node that is infected or protected keeps that state until the process ends.
The process ends as soon as the virus can no longer spread.

At most one node is protected per time step, and protecting no node at all is allowed.

The goal is to minimize the number of infected nodes when the process ends.

Example network

In the network above, node 1 has children 2 and 3, node 2 has the single child 4, and node 3 has children 5 and 6. At time 0 the virus infects the root, node 1. If node 3 is protected at time 1, the virus infects node 2. If node 4 is then protected at time 2, the virus can no longer spread and 2 nodes are infected. Protecting node 2 instead of node 3 at time 1 lets the virus infect node 3, and the number of infected nodes is again no smaller than 2. So the minimum for this network is 2.

Given a network in the form of a binary tree, write a program that computes the minimum possible number of infected nodes.

Input

The first line contains the number of nodes $n$ ( $1 \le n < 2^{20}$ ). Each of the next $n$ lines describes one node: the $i$ -th of these lines contains two integers, the left child and the right child of node $i$ . Nodes are numbered from 1 to $n$ , node 1 is the root, and 0 means there is no child.

Output

Print the minimum possible number of infected nodes on one line.

Examples7

Example 1
Input
```
6
2 3
4 0
5 6
0 0
0 0
0 0
```
Expected output
```
2
```
Example 2
Input
```
3
2 3
0 0
0 0
```
Expected output
```
2
```
Example 3
Input
```
4
3 2
0 0
0 4
0 0
```
Expected output
```
2
```
Example 4
Input
```
1
0 0
```
Expected output
```
1
```
Example 5
Input
```
2
0 2
0 0
```
Expected output
```
1
```
Example 6
Input
```
5
2 0
3 4
5 0
0 0
0 0
```
Expected output
```
1
```
Example 7
Input
```
7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
```
Expected output
```
3
```