406193: GYM102307 G Graduation

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Graduationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

It is time for Mr. Potato Head, the best student in his high school, to enter the university, he has chosen to study in the UNAL. In order for Mr. Potato Head to finish his studies he must take and pass $$$n$$$ courses.

In the UNAL every course can be prerequisite of at most another course, i.e. if a course A is a prerequisite of course B, Mr. Potato Head must pass the course A before taking the course B, when a course has no prerequisites it can be taken in any semester. Moreover, Mr. Potato Head knows that it is very hard to pass more than $$$k$$$ courses in a semester, therefore, no matter how many courses he can take in a semester, he will take at most $$$k$$$.

Given the list of courses that Mr. Potato Head must pass and the information about prerequisites, which is the minimum number of semesters that Mr. Potato Head must take to graduate from UNAL?

Input

The first line of input consist of integers $$$n$$$ $$$(1 \leq n \leq 10^4)$$$ and $$$k$$$ $$$(1 \leq k \leq 10)$$$ $$$-$$$ The number of courses Mr. Potato Head must pass and the maximum number of courses per semester Mr. Potato Head will take, respectively.

The following line consists of $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ separated by spaces, where the $$$i$$$-th course is the prerequiste of the course $$$a_i$$$. If the $$$i$$$-th course is not a prerequisite of any other course $$$a_i = 0$$$.

Output

Print a single integer $$$-$$$ The minimum number of semesters Mr. Potato Head needs to graduate.

ExamplesInput
4 2
3 3 4 0
Output
3
Input
3 3
0 1 2
Output
3
Note

It is guaranteed that Mr. Potato Head can graduate within the conditions above.

加入题单

上一题 下一题 算法标签: