시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 64 MB 97 35 30 37.037%

문제

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

6 2
5 5 0 5 0 5

예제 출력 1

2

힌트

W3sicHJvYmxlbV9pZCI6IjM2MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4NzFcdWJjZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzY3OFx1YWNjNFx1Yzc3OCBcdWQ1M2NcdWQxMzBcdWIyOTQgXHVhZGY4XHVjNzU4IFx1Yzg3MVx1YmNmNFx1Yjk3YyBcdWNkOTRcdWM4MDFcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWQ1M2NcdWQxMzBcdWIyOTQgXHViYTg3IFx1YzhmY1x1YjNkOVx1YzU0OCBcdWM1ZjRcdWMyZWNcdWQ3ODggXHVjNzkxXHVjNWM1XHVkNTc0IFx1Yzg3MVx1YmNmNFx1Yzc1OCBcdWJjYTBcdWQwYzAgXHViYzg0XHVjODNjXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODcxXHViY2Y0XHViOTdjIFx1YzBiNFx1ZDNiNFx1YmNmNFx1YjJjOCBcdWMxMjBcdWM4NzAgXHVjOTExIFx1Yzc3Y1x1YmQ4MFx1YWMwMCBcdWIxMDhcdWJiMzQgXHViOWNlXHVjNzQwIFx1YmQ4MFx1YmFhOFx1Yjk3YyBcdWFjMDBcdWM4NGNcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YWM4Y1x1YjQxOFx1YzVjOFx1YjJlNC4gKFx1YzY3OFx1YWNjNFx1Yzc3OCBkXHViYTg1XHVjNzU4IFx1YmQ4MFx1YmFhOFx1Yjk3YyBcdWFjMDBcdWM5YzRcdWIyZTQpIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWQ1M2NcdWQxMzBcdWIyOTQgXHViYTg3XHViYTg3Jm5ic3A7XHViZDgwXHViYWE4LVx1Yzc5MFx1YzJkZCBcdWFkMDBcdWFjYzRcdWIyOTQgXHVjMTIwXHVjODcwLVx1Yzc5MFx1YzE5MCBcdWFkMDBcdWFjYzRcdWM3N2MgXHVhYzgzXHVjNzc0XHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTNjXHVkMTMwXHVhYzAwJm5ic3A7XHVjODcxXHViY2Y0XHViOTdjIFx1YjljY1x1Yzg3MVx1YzJhNFx1YjdlY1x1YzZiNCBcdWQ2MTVcdWQwZGNcdWI4NWMgXHViYzE0XHVhZmI4XHViODI0XHViYTc0IFx1Y2Q1Y1x1YzE4YyBcdWJhODcgXHViYTg1XHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NTggXHViZDgwXHViYWE4XHVjNzU4IFx1YzIxOFx1YWMwMCBkXHViYTg1XHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWFjZTAsIFx1YWMwMSBcdWM2NzhcdWFjYzRcdWM3NzhcdWM3NzQgXHVjODcxXHViY2Y0XHVjNWQwIFx1ZDU1YyBcdWJjODhcdWI5Y2MgXHViMTc4XHVjZDljXHViNDFjIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWI5Y2NcdWM4NzFcdWMyYTRcdWI3ZWNcdWM2YjQgXHVkNjE1XHVkMGRjXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgZFx1YWMwMCAyXHVjNzc0XHVhY2UwIFx1ZDUzY1x1ZDEzMFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHVjODcxXHViY2Y0XHVjNzU4IFx1YmNhMFx1ZDBjMCBcdWJjODRcdWM4M2NcdWM3NzQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNFx1YmE3NCw8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9nZW5lMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjdweDsgd2lkdGg6NDA1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWMxMjBcdWM4NzAgXHViNDUwIFx1YmE4NVx1Yzc0NCBcdWNkOTRcdWFjMDBcdWQ1NThcdWJhNzQgXHViOWNjXHVjODcxXHVjMmE0XHViN2VjXHVjNmI0IFx1ZDYxNVx1ZDBkY1x1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZ2VuZTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU3cHg7IHdpZHRoOjQxMnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggblx1YWNmYyBkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBuICZsZTsgMTAwLDAwMCwgMiAmbGU7IGQgJmxlOyBuKSBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2QxZCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIGlcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4XHViMjk0IGlcdWJjODhcdWM5ZjggXHVjNzkwXHVjMmRkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTNjXHVkMTMwXHVjNzU4IFx1Yzg3MVx1YmNmNFx1YzVkMCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVjMTIwXHVjODcwXHViMjk0IFx1YmFhOFx1YjQ1MCAxXHViYzg4XHViZDgwXHVkMTMwIG5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVkNTNjXHVkMTMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAwXHViYzg4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzg3MVx1YmNmNFx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWMyYTRcdWI3ZWNcdWM2YjQgXHVkNjE1XHVkMGRjXHViODVjIFx1YmMxNFx1YWZiOFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJhODVcdWM3NDQgXHVjZDk0XHVhYzAwXHVkNTU4XHViYTc0IFx1YjQxOFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzYyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdlbmVhbG9neSIsImRlc2NyaXB0aW9uIjoiPHA+QWxpZW4gUGV0ZXIgd2FudHMgdG8gdHJhY2UgaGlzIGZhbWlseSBwZWRpZ3JlZXMuIFdvcmtpbmcgaGFyZCBmb3Igc2V2ZXJhbCB3ZWVrcywgaGUgaGFzIGNyZWF0ZWQgYSBiZXRhIHZlcnNpb24gb2YgaGlzIGZhbWlseSB0cmVlLiBVbmZvcnR1bmF0ZWx5LCBzb21lIG9mIGhpcyBhbmNlc3RvcnMgaGF2ZSB0b28gbXVjaCBwYXJlbnRzIGluIHRoaXMgdHJlZSAoYWxpZW5zIGhhdmUgZCBwYXJlbnRzKS4gU28gUGV0ZXIgdGhpbmtzIHRoYXQgc29tZSBvZiBwYXJlbnQtY2hpbGQgcmVsYXRpb25zIGFjdHVhbGx5IGFyZSBhbmNlc3Rvci1kZXNjZW5kYW50IHJlbGF0aW9ucy4gTm93IFBldGVyIHdhbnRzIHRvIGtub3csIHdoYXQgbWluaW1hbCBudW1iZXIgb2YgYW5jZXN0b3JzIG5lZWQgdG8gYmUgYWRkZWQgdG8gdGhlIHRyZWUgdG8gbWFrZSBpdCBsb29rIHdlbGwtZm9ybWVkIChmYW1pbHkgdHJlZSBsb29rcyB3ZWxsLWZvcm1lZCBpZiBlYWNoIGFsaWVuIGhhcyBubyBtb3JlIHRoYW4gZCBwYXJlbnRzLCBlYWNoIGFsaWVuIG11c3QgYXBwZWFyIGF0IHRoZSB0cmVlIG9ubHkgb25jZSkuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBpZiBkID0gMiwgYW5kIGJldGEtdmVyc2lvbiBvZiB0aGUgZmFtaWx5IHRyZWUgbG9va3MgbGlrZSB0aGlzOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2dlbmUxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyN3B4OyB3aWR0aDo0MDVweFwiIFwvPjxcL3A+XHJcblxyXG48cD50aGVuIFBldGVyIHNob3VsZCBhZGQgYXQgbGVhc3QgdHdvIGFuY2VzdG9ycyB0byBtYWtlIGl0IGxvb2sgd2VsbC1mb3JtZWQ6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZ2VuZTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU3cHg7IHdpZHRoOjQxMnB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5MZXQgUGV0ZXImcnNxdW87cyBhbmNlc3RvcnMsIGFwcGVhcmVkIGluIHRoZSBiZXRhLXZlcnNpb24gb2YgaGlzIGZhbWlseSB0cmVlLCBoYXZlIGlkZW50aVx1ZmIwMWVycyBmcm9tIDEgdG8gbiAobGV0IFBldGVyJnJzcXVvO3MgaWRlbnRpXHVmYjAxZXIgYmUgMCkuPFwvcD5cclxuXHJcbjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBcdWZiMDFsZSBjb250YWlucyBudW1iZXJzIG4gYW5kIGQgKDIgJmxlOyBuICZsZTsgMTAwIDAwMCwgMiAmbGU7IGQgJmxlOyBuKS4gVGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIG4gbnVtYmVycywgdGhlIGktdGggbnVtYmVyIGlzIGFuIGlkZW50aVx1ZmIwMWVyIG9mIHRoZSBjaGlsZCBvZiB0aGUgaS10aCBhbGllbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Xcml0ZSB0aGUgbWluaW1hbCBudW1iZXIgb2YgUGV0ZXImcnNxdW87cyBhbmNlc3RvcnMsIHRoYXQgc2hvdWxkIGJlIGFkZGVkIHRvIHRoaXMgdHJlZSB0byBtYWtlIGl0IGxvb2sgd2VsbCBmb3JtZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d