타치바나 셰리는 아주 조금 많이 힘이 세답니다!
어느 날, 셰리짱은 테라와 루루가 운영하는 과수원에 침입했어요. 셰리짱의 괴력을 자랑하기 위해서였죠!
과수원은 사과나무를 정점으로, 사과나무 사이의 길을 간선으로 하는 하나의 포레스트로 나타낼 수 있어요. 셰리짱은 한 번의 행동으로 현재 남아 있는 아무 컴포넌트(트리) 하나를 고를 수 있어요. 고른 컴포넌트의 지름의 길이를 라고 할 때, 셰리짱은 그 컴포넌트에서 원하는 사과나무를 최대 개 부술 수 있답니다! 이때 지름의 길이는 지름에 포함된 정점의 개수로 계산해요.
사과나무를 부수면 그 나무와 연결되어 있던 길도 함께 사라지고, 그 결과 남은 사과나무들이 여러 컴포넌트로 나뉠 수도 있어요.
에마씨에게 자랑하려면 최대한 빨리 모든 사과나무를 부숴야 해요. 셰리짱이 모든 사과나무를 부수기 위해 필요한 최소 행동 수를 구해주세요!
첫째 줄에 사과나무의 수 과 길의 수 이 공백으로 구분되어 주어집니다. (; )
첫째 줄에 셰리짱이 모든 사과나무를 부수기 위해 필요한 최소 행동 횟수를 출력해주세요!
이후 개의 줄에 걸쳐 두 정수 , 가 주어집니다. 이는 번 사과나무와 번 사과나무를 연결하는 길이 존재한다는 뜻이에요. (; )
같은 두 사과나무를 연결하는 길이 두 개 이상 주어지지 않습니다.
주어지는 그래프는 포레스트입니다.
| 5 | 12 |
| 6 | 18 |
| 7 | 55 | 추가 제한 없음 |
