310640: CF1863I. Redundant Routes

I. Redundant Routestime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given a tree with $n$ vertices labeled $1, 2, \ldots, n$. The length of a simple path in the tree is the number of vertices in it.

You are to select a set of simple paths of length at least $2$ each, but you cannot simultaneously select two distinct paths contained one in another. Find the largest possible size of such a set.

Formally, a set $S$ of vertices is called a route if it contains at least two vertices and coincides with the set of vertices of a simple path in the tree. A collection of distinct routes is called a timetable. A route $S$ in a timetable $T$ is called redundant if there is a different route $S' \in T$ such that $S \subset S'$. A timetable is called efficient if it contains no redundant routes. Find the largest possible number of routes in an efficient timetable.

Input

The first line contains a single integer $n$ ($2 \le n \le 3000$).

The $i$-th of the following $n - 1$ lines contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$) — the numbers of vertices connected by the $i$-th edge.

It is guaranteed that the given edges form a tree.

Output

Print a single integer — the answer to the problem.

ExamplesInput

4
1 2
1 3
1 4

Output

3

Input

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

Output

7

Note

In the first example, possible efficient timetables are $\{\{1, 2\}, \{1, 3\}, \{1, 4\}\}$ and $\{\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}\}$.

In the second example, we can choose $\{ \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 6\}, \{2, 3, 5\}, \{3, 4, 5\}, \{3, 4, 7\}, \{4, 6, 7\}\}$.

题目大意：
给定一棵有n个顶点（标记为1, 2, ..., n）的树，简单路径的长度是路径中的顶点数。需要选择一组简单路径，每条路径长度至少为2，但不能同时选择一个路径包含另一个路径的情况。求这样一个集合的最大可能大小。

正式地说，如果一组顶点S至少包含两个顶点并且与树中的简单路径的顶点集相同，则称S为“路线”。一组不同的路线称为“时间表”。如果时间表T中的路线S存在另一个不同的路线S' ∈ T，使得S ⊆ S'，则称路线S在时间表T中是“冗余”的。不包含冗余路线的时间表称为“有效”的。求有效时间表中可能的最大路线数量。

输入输出数据格式：
输入：
- 第一行包含一个整数n（2 ≤ n ≤ 3000）。
- 接下来的n-1行，每行包含两个整数u_i和v_i（1 ≤ u_i, v_i ≤ n，u_i ≠ v_i）——表示第i条边连接的两个顶点编号。
- 保证给定的边构成一棵树。

输出：
- 打印一个整数——问题的答案。

示例：
输入：
```
4
1 2
1 3
1 4
```
输出：
```
3
```

输入：
```
7
2 1
3 2
4 3
5 3
6 4
7 4
```
输出：
```
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\}\}\)。题目大意： 给定一棵有n个顶点（标记为1, 2, ..., n）的树，简单路径的长度是路径中的顶点数。需要选择一组简单路径，每条路径长度至少为2，但不能同时选择一个路径包含另一个路径的情况。求这样一个集合的最大可能大小。 正式地说，如果一组顶点S至少包含两个顶点并且与树中的简单路径的顶点集相同，则称S为“路线”。一组不同的路线称为“时间表”。如果时间表T中的路线S存在另一个不同的路线S' ∈ T，使得S ⊆ S'，则称路线S在时间表T中是“冗余”的。不包含冗余路线的时间表称为“有效”的。求有效时间表中可能的最大路线数量。 输入输出数据格式： 输入： - 第一行包含一个整数n（2 ≤ n ≤ 3000）。 - 接下来的n-1行，每行包含两个整数u_i和v_i（1 ≤ u_i, v_i ≤ n，u_i ≠ v_i）——表示第i条边连接的两个顶点编号。 - 保证给定的边构成一棵树。 输出： - 打印一个整数——问题的答案。 示例： 输入： ``` 4 1 2 1 3 1 4 ``` 输出： ``` 3 ``` 输入： ``` 7 2 1 3 2 4 3 5 3 6 4 7 4 ``` 输出： ``` 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\}\}\)。