Byteland Network Reliability Improvement

The government of Byteland is finally ready to connect all of its computers to the Internet. However, the network was built as a tree with N computers and exactly N-1 direct links. This means that if any single link fails, the network will be split into two disconnected parts.

Your task is to help by finding the minimum number of additional links that need to be added to the network so that it remains connected even if any one link is removed. It can be proven that for a tree, the answer is equal to \(\lceil \frac{L}{2} \rceil\), where \(L\) is the number of leaf nodes. A leaf node is a node with degree 1.

Note: The computers are numbered from 1 to N.

inputFormat

The first line contains a single integer N (1 \(\leq\) N \(\leq\) 10⁵), the number of computers. Each of the following N-1 lines contains two integers \(u\) and \(v\) (1 \(\leq\) u, v \(\leq\) N) meaning that there is a direct link between computer \(u\) and computer \(v\).

outputFormat

Output a single integer, the minimum number of additional links needed such that the network remains connected if any single link is removed.

sample

4
1 2
2 3
3 4

1