시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB62240.000%

문제

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.

입력

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$

서브태스크

번호배점제한
15

$N ≤ 10$

210

$N ≤ 100$

315

$N ≤ 3000$

415

$N ≤ 300\,000$, there is at most one city with at least 3 highways connected to it.

555

-

예제 입력 1

4
1 2
1 3
3 4


예제 출력 1

3


It is impossible to increase the largest distance beyond 3.

This testcase is valid for all subtasks.

예제 입력 2

6
1 2
2 3
2 5
4 5
5 6


예제 출력 2

5


We may remove highway 2-5, and add the highway 3-4, so that the longest path becomes 1 − 2 − 3 − 4 − 5 − 6.

This testcase is valid for subtasks 1, 2, 3 and 5.

채점 및 기타 정보

• 예제는 채점하지 않는다.