题目描述

给定一棵包含 $n$ 个点的无权树，点的编号为 $1$ 到 $n$。树上两点的距离定义为它们之间唯一简单路径上的边数。

选择两个不同的点作为关键点。对于每个点 $i$，令 $dis[i]$ 为它到两个关键点的距离中的较小值。求所有选法中 $\max_{1\leq i\leq n}dis[i]$ 的最小值。

输入格式

从文件 tree.in 中读取数据。

第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行包含两个整数 $x,y$（$1\leq x,y\leq n$），表示点 $x$ 与点 $y$ 之间有一条无向边。保证这些边构成一棵树。

输出格式

将结果输出到文件 tree.out 中。

输出一个整数，表示最小的最大距离。

样例

5
1 2
2 3
3 4
4 5

1

8
1 2
1 3
2 4
2 5
3 6
3 7
1 8

2

数据规模与约定

对于前 $30 \%$ 的数据， $n \leq 300$ 。

对于前 $50 \%$ 的数据， $n \leq 5000$ 。

另有 $20 \%$ 的数据，保证树的形态随机，$n=199973$。

对于 $100 \%$ 的数据, 保证 $3 \leq n \leq 200000$ 。