4390 - 第九课:树上染色

给定一棵n个结点的树, 以1为根。

现在需要给每个结点染色,如果三个结点$a, b, c $, a与b相连,b与c相连, 那么$a, b, c$的颜色互不相同。

问最少需要几种颜色能将整棵树染色。

输入

第一行输入一个整数$ n (3 \le n \le 2*10^5) $。

接下来$n−1$行每行两个整数$x, y (1 \le x, y \le n, x \ne y)$表示一条树边。

输出

输出一个整数表示最少需要的颜色数量。

样例

输入

3
2 3
1 3

输出

3

输入

5
2 3
5 3
4 3
1 3

输出

5
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题