Bessie's Vacation Visits

After many weeks of hard work, Bessie is finally getting a vacation! As the most sociable cow, she wants to visit her N friends, numbered from 1 to N (1 \leq N \leq 50000). These friends are connected by exactly N-1 roads, each linking a pair of cows, forming a tree structure. There is a unique path between any two cows.

However, Farmer John has imposed a restriction: if two cows are directly connected by a road, Bessie may not visit both. Bessie wants her vacation to be as long as possible, so she must choose a set of cows to visit such that no two visited cows are directly connected by a road. Your task is to help Bessie determine the maximum number of cows she can visit.

Solve this problem using an efficient algorithm (for example, tree dynamic programming) that computes the maximum independent set on a tree.

inputFormat

The first line of input contains an integer N representing the number of cows.

Each of the next N-1 lines contains two integers, C1 and C2 (1 \leq C1, C2 \leq N and C1 \neq C2), indicating that there is a road between cow C1 and cow C2.

outputFormat

Output a single integer, the maximum number of cows Bessie can visit under the restriction.

sample

1

1