atcoder#AGC004D. [AGC004D] Teleporter
[AGC004D] Teleporter
Score : points
Problem Statement
There are towns in Snuke Kingdom, conveniently numbered through . Town is the capital.
Each town in the kingdom has a Teleporter, a facility that instantly transports a person to another place. The destination of the Teleporter of town is town (). It is guaranteed that one can get to the capital from any town by using the Teleporters some number of times.
King Snuke loves the integer . The selfish king wants to change the destination of the Teleporters so that the following holds:
- Starting from any town, one will be at the capital after using the Teleporters exactly times in total.
Find the minimum number of the Teleporters whose destinations need to be changed in order to satisfy the king's desire.
Constraints
- One can get to the capital from any town by using the Teleporters some number of times.
Input
The input is given from Standard Input in the following format:
Output
Print the minimum number of the Teleporters whose destinations need to be changed in order to satisfy King Snuke's desire.
3 1
2 3 1
2
Change the destinations of the Teleporters to .
4 2
1 1 2 2
0
There is no need to change the destinations of the Teleporters, since the king's desire is already satisfied.
8 2
4 1 2 3 1 2 3 4
3
For example, change the destinations of the Teleporters to .