시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 78 29 24 38.710%

문제

외계인 피터는 그의 족보를 추적하려고 한다. 피터는 몇 주동안 열심히 작업해 족보의 베타 버젼을 만들었다.

족보를 살펴보니 선조 중 일부가 너무 많은 부모를 가졌다는 사실을 알게되었다. (외계인 d명의 부모를 가진다) 그래서 피터는 몇몇 부모-자식 관계는 선조-자손 관계일 것이라고 생각했다.

피터가 족보를 만족스러운 형태로 바꾸려면 최소 몇 명을 추가해야 하는지 구하는 프로그램을 작성하시오.

각각의 외계인의 부모의 수가 d명을 넘지 않고, 각 외계인이 족보에 한 번만 노출된 경우에 만족스러운 형태라고 한다.

예를 들어, d가 2이고 피터가 만든 족보의 베타 버젼이 아래와 같다면,

아래와 같이 선조 두 명을 추가하면 만족스러운 형태가 된다.

입력

첫째 줄에 두 정수 n과 d가 주어진다. (2 ≤ n ≤ 100,000, 2 ≤ d ≤ n) 다음 줄에는 총 n개의 정수가 주어지며, i번째 정수는 i번째 자식의 번호이다.

피터의 족보에 등장하는 선조는 모두 1번부터 n번까지 번호로 나타낸다. 피터의 번호는 0번이다.

출력

족보를 만족스러운 형태로 바꾸기 위해서 최소 몇 명을 추가하면 되는지 출력한다.

예제 입력

6 2
5 5 0 5 0 5

예제 출력

2

힌트