차원의 나무 여행

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

요약

트리가 주어질 때, 각 이동이 인접하지 않은 정점으로 가고 정점을 한 번씩만 방문하는 경로의 최대 길이를 구합니다.

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

문제

정점의 개수가 $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
```