Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Genealogy
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 3181Accepted: 937

Description

Alien Peter wants to trace his family pedigrees. Working hard for several weeks, he has created a beta-version of his family tree. Unfortunately, some of his ancestors have too much parents in this tree (aliens have d parents). So Peter thinks that some of parent-child relations actually are ancestor-descendant relations. Now Peter wants to know, what minimal number of ancestors need to be added to the tree to make it look well-formed (family tree looks well-formed if each alien has no more than d parents, each alien must appear at the tree only once).

For example, if d = 2, and beta-version of the family tree looks like this:

then Peter should add at least two ancestors to make it look well-formed:

Input

Let Peter’s ancestors, appeared in the beta-version of his family tree, have identifiers from 1 to n (let Peter’s identifier be 0).

The first line of input file contains numbers n and d (2 ≤ n ≤ 100 000, 2 ≤ dn). The following line contains n numbers, the i-th number is an identifier of the child of the i-th alien.

Output

Write the minimal number of Peter’s ancestors, that should be added to this tree to make it look well-formed.

Sample Input

6 2
5 5 0 5 0 5

Sample Output

2

Source

Northeastern Europe 2006, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator