A country consists of N cities. These cities are connected with each other using N−1 bidirectional roads that are in the form of a tree. Each city is numbered from 1 to N.
You want to safeguard all the roads in the country from any danger, and therefore, you decide to place cameras in certain cities. A camera in a city can safeguard all the roads directly connected to it.
Your task is to determine the minimum number of cameras that are required to safeguard the entire country.
Input Format:
Output Format:
Print a single integer that represents the minimum number of cameras required to safeguard the country.
Constraints:
1≤N≤2×1051≤u,v≤N
City 1 is connected to all the other cities in the country. If you place a camera in city 1, then all the cities and roads are safeguarded. Hence, the minimum number of cameras required is 1.