링크

학교 웹사이트를 정리하려고 한다. 웹사이트에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 페이지가 있으며, 홈페이지는 $1$번 페이지이다. 내용은 문제가 없지만 링크 구조가 좋지 않다. 모든 페이지에는 정확히 하나의 링크가 있고, 그 링크는 자기 자신이 아닌 다른 페이지를 가리킨다. 그래서 홈페이지에서 출발한 방문자가 원하는 페이지에 도달하려면 링크를 여러 번 따라가야 하는 경우가 많고, 홈페이지에서 아예 도달할 수 없는 페이지도 있을 수 있다.

이를 해결하기 위해 새 링크를 어디에나 추가할 수 있다. 즉, 어떤 페이지에든 새 링크를 만들 수 있고 그 링크는 임의의 페이지를 가리킬 수 있다. 정수 $K$에 대해, 홈페이지를 제외한 모든 페이지를 홈페이지에서 링크를 최대 $K$번 따라가서 도달할 수 있으면 그 웹사이트를 $K$-도달 가능하다고 한다.

웹사이트의 구조와 정수 $K$가 주어질 때, 웹사이트를 $K$-도달 가능하게 만들기 위해 추가해야 하는 링크의 최소 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 두 정수 $N$과 $K$가 주어진다 ($2 \le N \le 500\,000$, $1 \le K \le 20\,000$). 각각 페이지의 수와 방문자가 따라갈 수 있는 링크의 최대 횟수이다.

다음 $N$개의 줄에는 서로 다른 두 정수 $A$와 $B$가 주어진다 ($1 \le A, B \le N$). 이는 $A$번 페이지의 링크가 $B$번 페이지를 가리킨다는 뜻이다.

웹사이트를 $K$-도달 가능하게 만들기 위해 추가해야 하는 링크의 최소 개수를 한 줄에 출력한다.