Tree Cutting

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

요약

트리에서 간선 하나를 지우고 두 조각을 새 간선으로 이어 붙여 트리의 지름이 최대가 되도록 만들고, 그 지름을 구한다.

난이도: 보통10점 중 7점
유형: 트리, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

A country has $N$ cities numbered from $1$ to $N$ and $N - 1$ bidirectional highways. It is possible to travel from any city to any other city using only the highways.

The distance between two cities $x$ and $y$ is defined as the number of highways required to travel from $x$ to $y$ .

The governor has decided to demolish a highway and build another highway such that the largest distance between any two cities is maximized.

Find this maximum largest distance.

입력

Your Program must read from standard input.

The first line contains an integer, $N$ , the number of cities.

In the next $N - 1$ lines, each line contains $2$ distinct integers $u$ and $v$ , representing a highway connecting cities $u$ and $v$ .

출력

Your program must print to standard output.

The output should contain a single integer on a single line, the new largest distance between any two cities.

제한

$3 ≤ N ≤ 300\\,000$
$1 ≤ u, v ≤ N$

예제2

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