给你一棵树,其中 $$$n$$$ 个顶点标记为 $$$1, 2, \ldots, n$$$。树中简单路径的长度是其中的顶点数。
您要选择一组长度至少为 $$$2$$$ 的简单路径,但不能同时选择两个相互包含的不同路径。找出这样一个集合的最大可能大小。
正式来说,如果一个顶点集 $$$S$$$ 包含至少两个顶点并且与树中简单路径的顶点集一致,则该顶点集称为路径。不同路线的集合称为时间表。如果 T$$$ 中有一条不同的路线 $$$S' \in T$$$ 使得 $$$S \子集 S'$$$,则时间表 $$$T$$$ 中的路线 $$$S$$$ 被称为冗余路线。如果一个时间表不包含冗余路线,则该时间表被称为有效的。在有效的时间表中找到尽可能多的路线。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$)。
以下 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) — 第 $$$i$$$ 连接的顶点数边缘。
保证给定的边形成一棵树。
输出
打印一个整数——问题的答案。
示例
输入 #1
4 1 2 1 3 1 4
输出 #1
3
输入 #2
7 2 1 3 2 4 3 5 3 6 4 7 4
输出 #2
7
注意
在第一个示例中,可能的有效时间表是 $$$\{\{1, 2\}、\{1, 3\}、\{1, 4\}\}$$$ 和 $$$\{\{1, 2, 3\}、\{1, 2, 4\}、\{1, 3, 4\}\}$$$。
在第二个示例中,我们可以选择 $$$\{ \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 6\}, \{2, 3, 5\}, \{3, 4, 5\}, \{3, 4, 7\}, \{4, 6, 7\}\}$$$。