Tree tearing
92% Success1146 Attempts50 Points1s Time Limit256MB Memory1024 KB Max Code
You are given a tree consising of N vertices. What is the minimum number of vertices that should be removed that all the remaining parts of the initial tree will contain less than K vertices?
Input
The first line contains one integer K.
The second line contains one integer N.
The third line contains N-1 space-separated intgers ai for 2 <= i <= N which means that vertices i and ai are connected by an edge.
Output
Output one number - answer for the question.
Constraints
- 1 <= K, N <= 10 000
- ai < i
Examples
Input
3 12 1 1 2 2 3 2 3 6 6 6 7
Output
3
Explanation
We can remove vertices 2, 3, 6.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Loading Editor...
Results