순찰

$1$번부터 $N$번까지 번호가 붙은 $N$개의 마을이 있고, 이 마을들을 모두 연결하는 $N-1$개의 도로가 있다. 각 도로는 정확히 두 마을을 연결하며, 임의의 마을에서 이 도로들만 이용하여 다른 모든 마을로 갈 수 있다(즉, 도로들은 트리를 이룬다). 각 도로의 길이는 $1$이다.

모든 마을 사람들의 안전을 위해 순찰대는 매일 모든 도로를 지나가야 한다. 경찰서는 마을 $1$에 있으므로, 순찰대는 매일 마을 $1$에서 출발하여 마지막에 다시 마을 $1$로 돌아와야 한다. 하루의 임무를 마치려면 순찰대는 각 도로를 정확히 두 번씩 지나가야 하며, 따라서 트리에서의 전체 거리는 $2(N-1)$이다. 예를 들어 어떤 $8$개 마을의 트리에서 이 거리는 $14$이다.

순찰대가 지나가야 하는 전체 거리를 줄이기 위해, 마을들 사이에 $K$개의 지름길을 새로 건설한다. 각 지름길은 두 마을을 잇는 길이 $1$의 새 도로이다. 두 지름길이 같은 마을에서 시작할 수도 있고, 지름길이 루프일 수도 있다(즉, 한 마을을 자기 자신과 연결할 수 있다). 예산이 제한되어 있으므로 $K$는 $1$ 또는 $2$이다. 또한 돈이 낭비되지 않도록, 순찰대는 하루에 각 지름길을 정확히 한 번씩 지나가야 한다.

위의 $8$개 마을 트리에서, 지름길 하나를 잘 놓으면 순찰대의 전체 거리는 $11$로 줄어들고, 지름길 두 개를 놓으면 $10$까지 줄일 수 있다. 그러나 지름길 두 개를 잘못 놓으면, 순찰대가 각 지름길을 정확히 한 번씩 지나가야 한다는 조건 때문에 전체 거리가 오히려 $14$보다 커질 수도 있다(예: $15$).

도로 정보와 건설할 지름길의 수 $K$가 주어질 때, 순찰대가 매일 지나가야 하는 전체 거리가 최소가 되도록 지름길을 어디에 놓을지 결정하여 그 최솟값을 출력하는 프로그램을 작성하라.

첫째 줄에 두 정수 $N$($3 \le N \le 100000$)과 $K$($1 \le K \le 2$)가 주어진다.

이어지는 $N-1$개의 줄에는 각각 두 정수 $A$와 $B$($1 \le A, B \le N$)가 주어지며, 이는 마을 $A$와 마을 $B$를 잇는 도로가 있음을 뜻한다.

지름길 $K$개를 최적으로 건설했을 때 순찰대가 매일 지나가야 하는 전체 거리의 최솟값을 정수 하나로 한 줄에 출력한다.