차원의 나무 여행

시간 제한1초메모리 제한1024 MB

요약

정점 N개짜리 트리에서 간선으로 연결되지 않은 정점으로 이동하는 워프를 최대로 몇 번 할 수 있는지 구한다. 시작 정점을 고르는 것도 워프 한 번으로 센다.

난이도: 보통10점 중 6점
유형: 트리, 동적 계획법, 그리디, DFS
정답자: 아직 제출이 없습니다

문제

정점의 개수가 $N$ , 간선의 개수가 $N-1$ 인 트리가 주어진다. 간선으로 직접 연결되지 않은 정점으로 이동하는 것을 워프라고 한다. 각 정점을 최대 한 번만 방문할 수 있을 때, 가능한 워프의 최대 횟수를 구하여라. 시작 정점은 임의로 고를 수 있으며, 시작 정점을 고르는 것도 워프이다.

입력

첫 번째 줄에 $N$ 이 주어진다.

두 번째 줄부터 $N-1$ 개의 줄에 걸쳐 간선의 정보가 주어진다. 간선은 $u$ , $v$ 의 형태로 주어진다. 이는 트리의 $u$ 번 정점과 $v$ 번 정점이 간선으로 연결되어 있음을 의미한다.

출력

첫 번째 줄에 가능한 워프의 최대 횟수를 출력한다.

제한

$2 \le N \le 500$
$1 \le u, v \le N$

예제3

예제 1
입력
```
3
1 2
2 3
```
예상 출력
```
2
```
예제 2
입력
```
4
1 2
1 4
2 3
```
예상 출력
```
4
```
예제 3
입력
```
4
1 2
2 3
2 4
```
예상 출력
```
3
```