스키 최적화

Simone는 스웨덴 북부의 매우 높고 눈 덮인 산 정상에 산다. Simone가 정상에 있는 자신의 집에서 산의 다른 어떤 장소로 가고 싶을 때, 몇몇 장소 사이에 있는 단방향 리프트 시스템을 이용할 수 있다.

현재 산의 각 장소에는 Simone를 산의 다른 어떤 장소로 데려다주는 리프트가 정확히 하나씩 있다 (그녀는 보통 걸어서 집으로 돌아온다). 하지만 이 때문에 이동에는 많은 시간이 걸린다. Simone가 집에서 목적지까지 타야 할 수도 있는 리프트의 수가 정말 많을 수 있기 때문이다.

최근 Simone는 산에 더 많은 리프트를 건설하여 산의 관광 산업을 더욱 활성화하기 위해 스웨덴 산악 오락 협회(SAME)로부터 큰 보조금을 받았다. 하지만 Simone는 관광에는 별로 관심이 없고, 그저 더 빠르게 이동할 수 있기를 원한다. 사실 그녀는 목적지가 어디든 집에서 출발해 $K$개보다 많은 리프트를 이용해야 하는 일이 없기를 원한다.

그녀는 보조금으로 이 일을 충당할 수 있을지 궁금해하며, 따라서 건설해야 하는 새 리프트의 수를 계산해 달라고 요청했다.

점수

여러 테스트 케이스 그룹으로 해답을 평가한다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한 조건

$1$ |$19$| $N \leq 150, K \leq 10$

$2$ |$24$| $N \leq 5000, K \leq 20$

$3$ |$37$| $N \leq 10^5$

$4$ |$20$| 추가 제한 조건이 없다.

입력의 첫째 줄에는 두 정수 $N$와 $K$ ($2 \le N \leq 5 \cdot 10^5$, $1 \le K \leq 2 \cdot 10^4$)가 주어진다. 이는 각각 산에 있는 장소의 수와 Simone가 이용하고자 하는 리프트 수의 최댓값이다. 장소에는 $1$부터 $N$까지 번호가 매겨져 있으며, 그녀의 집 번호는 $1$이다.

이어지는 $N$개의 줄에는 두 정수 $1 \le A \not= B \le N$가 주어지며, 이는 Simone를 장소 $A$에서 장소 $B$로 데려다주는 리프트가 있다는 뜻이다.

정수 하나를 출력한다. Simone가 건설해야 하는 리프트 수의 최솟값이다.