Background

Xiao V (小 v) takes his cute little sister out to play. The sister wants to go to a maid cafe, while Xiao V wants to go to a board game bar.

Sister: "I’ll ask you a question. If you get it wrong, you’ll be my slave for a day. If you get it right, I’ll listen to you for the whole day."

Xiao V: "You’ll listen to me for everything!?"

Sister: "Heehee, you’d better just answer the question!"

To secure a happy day for himself, Xiao V comes to you for help.

Problem 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