Minimum Camera Cover in a Tree

An office building is represented as a tree with \(N\) nodes and \(N-1\) hallways (edges) connecting them. Each node is a room that must be monitored by at least one surveillance camera. A camera placed in a room can monitor itself and all directly adjacent rooms (neighbors).

Your task is to determine the minimum number of cameras required to monitor all rooms in the building.

Note: The tree is undirected. The input gives the number of nodes \(N\) and then \(N-1\) pairs of integers representing the edges. Use a depth-first search (DFS) strategy that considers three states for each node:

• \(0\): The room is not covered by any camera.
• \(1\): A camera is installed in this room.
• \(2\): The room is covered (monitored) by one of its adjacent rooms' cameras.

If after processing the tree the root remains uncovered, you must add an extra camera.

inputFormat

The input is read from standard input (stdin) and has the following format:

N
u1 v1
u2 v2
...
un-1 vn-1

Where \(N\) is the number of nodes in the tree, and each of the following \(N-1\) lines contains two integers \(u\) and \(v\) indicating an undirected edge between room \(u\) and room \(v\).

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of cameras required to monitor all the rooms.

## sample

6
1 2
1 3
5 2
6 2
2 4

2