Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0158 - GENEALOGY

   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 d n).  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.

Examples

stdin

stdout

1

6 2

5 5 0 5 0 5

2

 


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-04-09
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.Northern QF 2006.G

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.