← 返回题目列表

Codeforces · 1338/D

D. 嵌套橡皮筋

中文机器翻译题面 查看原题

你有一棵有 $$$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$$$ 或更多嵌套橡皮筋的序列。

您可以看到下面第二个示例的可能转换之一。