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 \le N \le 2 \times 10^5 \\ 1 \le u, v \le 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.