W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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 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 .
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.
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.