Ancient Castle Surveillance

In an ancient castle, the roads form an unrooted tree. Bob wants to place the minimum number of soldiers at some nodes of the tree such that every road (edge) is under surveillance. Note that if a soldier is placed at a node, all roads incident to that node are covered.

Your task is to compute the minimum number of soldiers Bob needs to place so that every road in the castle is observed.

This problem can be mathematically formulated as finding a minimum vertex cover on a tree. In other words, if we denote the set of nodes selected by S, then for every edge \( (u,v) \) in the tree, at least one of \( u \) or \( v \) must be in \( S \). The goal is to minimize \( |S| \).

inputFormat

The first line contains a single integer n (1 \(\le\) n \(\le\) 10⁵), the number of nodes in the tree.

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

outputFormat

Output a single integer, the minimum number of soldiers needed to surveil all roads.

sample

3
1 2
1 3

1