Partitioning the Tree into Good Subsets

You are given a tree \(T\) with \(n\) nodes. The tree is rooted at \(1\). Define \(\mathrm{subtree}(u)\) as the set of nodes in the subtree of \(u\).

Call a subset of nodes \(S\) good if and only if \(S\) satisfies at least one of the following conditions:

• For all \(u, v \in S\) with \(u \neq v\), either \(u \in \mathrm{subtree}(v)\) or \(v \in \mathrm{subtree}(u)\).
• For all \(u, v \in S\) with \(u \neq v\), both \(u \notin \mathrm{subtree}(v)\) and \(v \notin \mathrm{subtree}(u)\).

You need to partition all nodes of \(T\) into several good subsets. Calculate the minimum number of subsets required.

inputFormat

The first line contains an integer \(n\) \( (1 \le n \le 10^5) \) representing the number of nodes in the tree \(T\).

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), representing an edge between nodes \(u\) and \(v\) in the tree.

outputFormat

Output a single integer: the minimum number of good subsets into which the tree can be partitioned.

sample

5
1 2
1 3
2 4
2 5

2