1부터 N 까지 번호가 붙여진 N 개의 마을과, 이들 마을을 모두 연결하는 N - 1 개의 도로가 있다. 각 도로는 정확히 두 마을을 연결하며, 임의의 마을로부터 다른 모든 마을까지 이들 도로들만 이용하여 갈 수 있다. 각 도로의 길이는 1이다.

이들 모든 마을에 있는 사람들의 안전을 보장하기 위하여 순찰대가 매일 모든 도로를 방 문하여야 한다. 경찰서는 마을 1에 있다. 그러므로 경찰관은 매일 마을 1에서 출발하여 마 지막으로 마을 1로 돌아와야 한다.

8개의 마을로 구성된 아래의 예를 보자. 마을은 동그라미로 표시되어 있고, 경찰서가 있 는 마을 1은 검은색 동그라미로 표시되어 있다. 마을을 연결하는 선분은 도로를 나타낸다. 순찰대가 매일 모든 도로를 방문하기 위하여, 순찰대가 방문해야 하는 전체거리는 14이다. 순찰대는 하루의 임무를 완성하기 위하여 각 도로를 2번만 방문해야 함에 유의하라.

순찰대가 모든 도로를 방문하는데 필요한 전체거리를 줄이기 위하여 이들 마을 사이에 K 개의 지름길을 새로 만들기로 하였다. 각 지름길은 두 개의 마을을 연결한다. 두 지름길이 같은 마을에서 시작할 수 있다(아래 예 (c) 참고). 심지어 지름길이 루프일 수 있다; 즉 마 을 자신을 연결할 수 있다. 예산이 제한되어 있으므로, K 는 1 혹은 2이다. 또한, 돈이 쓸데없이 낭비되지 않도록 하 기 위하여 순찰대는 하루에 각 지름길을 정확하게 한번 방문하여야 한다.

다음의 예를 보자.

예 (a)에서는 지름길 하나를 건설한 것으로 순찰대가 방문하는 도로의 전체 길이는 11이 다. 예 (b)에서는 지름길 두 개를 건설한 것으로, 순찰대가 방문하는 도로의 전체 길이는 10이다. 예 (c)에서는 지름길을 두 개 건설하였는데 순찰대가 방문하는 도로의 전체 길이는 15이다. 이는 순찰대가 각 지름길을 정확하게 한번 지나가야 하는 조건 때문이다.

마을사이의 도로와 건설하여야 할 지름길의 수를 읽어 매일 순찰대가 방문하여야 하는 전 체 거리를 최소하도록 하기위하여 지름길을 어디에 건설해야하는지를 구하는 프로그램을 작 성하시오.

입력

출력

입출력 예

입력

8 1 
1 2
3 1
3 4
5 3
7 5
8 5
5 6

출력

11


입력 

8 2 
1 2
3 1
3 4
5 3
7 5
8 5
5 6

출력

10

입력 

5 2 
1 2
2 3
3 4
4 5

출력

6

제약조건

• 테스트 경우의 10%가 ≤ 1,000 , = 1 이다.
• 테스트 경우의 30%가 K = 1藍甄
• 테스트 경우의 80%가 각 마을에 인접한 마을의 최대 수가 25이하이다.
• 테스트 경우의 90%가 각 마을에 인접한 마을의 최대 수가 150이하이다.
• 테스트 경우의 100%가 3 ≤ N ≤ 100,000 이고, ≤ K ≤ 2聆甄

출처: Asia-Pacific Informatics Olympiad 2010