Fire Extinguishers

Memory limit: 64 MB

Byteasar has had a new palace built. It consists of chambers and corridors connecting them. Each corridor connects exactly two chambers. The rooms are numbered from to . There is only a single entrance to the palace, which leads to chamber no. . For each chamber there is exactly one route leading to it from the entrance, without turning back on the way. In other words, the chambers and the corridors form a tree - a connected acyclic graph.

The fire marshal who is to approve the building demands placing fire extinguishers inside. The following are his exact requirements:

• The fire extinguishers should be placed in (some) chambers, and one chamber may store any number of extinguishers.
• Each chamber has to be assigned one fire extinguisher, though it may be stored in another chamber.
• Each fire extinguisher can be assigned to at most different chambers.
• For each room its assigned extinguisher is within the range of corridors.

Input

The first line of the standard input contains three integers , and separated by single spaces, , , . Each of the following lines holds two integers separated by a single space. Line no. contains the numbers denoting the corridor connecting chambers no. and .

Output

The first and only line of the standard output is to hold one integer - the minimum number of fire extinguishers that have to be installed in palace.

Example

For the input data:

12 3 1
1 12
3 8
7 8
8 9
2 12
10 12
9 12
4 8
5 8
8 11
6 8

the correct result is:

4

Task author: Pawel Parys.