你有一棵有 $$$n$$$ 个顶点的树。您将把这棵树转换成无限大平面上的 $$$n$$$ 橡皮筋。转换规则如下:
- 对于每对顶点 $$$a$$$ 和 $$$b$$$,橡皮筋 $$$a$$$ 和 $$$b$$$ 应该相交,当且仅当树中 $$$a$$$ 和 $$$b$$$ 之间存在边时。
- 橡皮筋的形状必须是简单的环形。换句话说,橡皮筋是一个不自相交的环。
现在让我们定义以下内容:
- 橡皮筋 $$$a$$$ 包括橡皮筋 $$$b$$$,当且仅当橡皮筋 $$$b$$$ 在橡皮筋 $$$a$$$ 的区域内,并且它们彼此不相交。
- 橡皮筋序列 $$$a_{1}, a_{2}, \ldots, a_{k}$$$ ($$$k \ge 2$$$) 是嵌套的,当且仅当对于所有 $$$i$$$ ($$$2 \le i \le k$$$),$$$a_{i-1}$$$ 包括$$$a_{i}$$$。
这是转换的示例。请注意,橡皮筋 $$$5$$$ 和 $$$6$$$ 是嵌套的。
可以证明,在给定的约束条件下,是否可以对嵌套橡皮筋进行转换和排序。
从给定的树中可以获得的嵌套橡皮筋序列的最大长度是多少?找到并打印它。
输入
第一行包含整数 $$$n$$$ ($$$3 \le n \le 10^{5}$$$) — 树中的顶点数。
接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 包含两个整数 $$$a_{i}$$$ 和 $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le n$$$) - 这意味着 $$$a_{i}$$$ 和 $$$a_{i}$$$ 之间有一条边$$$b_{i}$$$。保证给定的图形成 $$$n$$$ 个顶点的树。
输出
打印答案。
示例
输入 #1
6 1 3 2 3 3 4 4 5 4 6
输出 #1
4
输入 #2
4 1 2 2 3 3 4
输出 #2
2
注意
在第一个示例中,您可以通过如下所示的转换获得 $$$4$$$ 橡皮筋的嵌套序列($$$1$$$、$$$2$$$、$$$5$$$ 和 $$$6$$$)。当然,还存在其他转换来制作 $$$4$$$ 橡皮筋的嵌套序列。但是,您无法使用给定的树创建 $$$5$$$ 或更多嵌套橡皮筋的序列。
您可以看到下面第二个示例的可能转换之一。