Description

Xiao V’s world is organized as a tree. At each node, you may build a maid cafe, a board game bar, or leave it empty. After fixing node $1$ as the root, the planning bureau requires: for every non-leaf node $i$, let $cafe_i$ be the number of maid cafes and $table_i$ be the number of board game bars in its subtree (including itself). It must hold that $cafe_i = table_i$.

The sister’s question is: what is the maximum number of maid cafes that can be placed on this tree?

Input Format

The first line contains a positive integer $n$, the number of nodes in the world.

Lines $2$ through $n$ each contain two positive integers $u$, $v$, indicating that there is an edge between $u$ and $v$.

Output Format

Output a single line with the maximum possible number of maid cafes.

5
1 2
2 3
3 4
2 5

2

Hint

Constraints

• For $30\%$ of the testdata, it is guaranteed that $n \le 20$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^5$, $1 \le u, v \le n$.

Translated by ChatGPT 5