eolymp
Competitions

2019 Fall KBTU OPEN

Kill all termites

There are termites on the tree. Your task is to kill them all. The tree is an undirected connected graph with n vertices and n - 1 edges. In order to kill termites you are able to poison some vertices. If the termite hits the vertex with poison, then he immediately dies. You don’t know where termites are located initially. But you know that termites go to the random adjacent vertex each time, but if termite has passed edge (u, v), next edge should be different from (v, u), except the case, when termite hits the leaf (in this case, termite turns around and goes back). You need to poison minimum number of vertices, such that termites hits poisoned vertices after finite number of steps.

Input

On the first line you are given single integer n (1n100000). On the next line you are given n - 1 integers pi (2in), so there is an edge connecting pi and i.

Output

On the single line output single integer - minimum number of poisoned vertices.

Time limit 1 second
Memory limit 128 MiB
Input example #1
1
Output example #1
1
Input example #2
2
1
Output example #2
1
Input example #3
8
1 1 2 1 2 3 2
Output example #3
2
Source 2019 Fall KBTU OPEN, Problem H