Dimensional Tree Trip

Time limit1sMemory limit1024 MB

Summary

Given a tree, find the longest sequence of distinct vertices where each step moves to a vertex not adjacent to the current one, counting the start as a warp.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, Graph
Solved: No attempts yet

Problem

A tree with $N$ vertices and $N-1$ edges is given. Moving to a vertex that is not directly connected to the current vertex by an edge is called a warp. Each vertex can be visited at most once. Find the maximum number of possible warps. The starting vertex can be chosen freely, and choosing the starting vertex also counts as a warp.

Input

The first line contains $N$ . The next $N-1$ lines each contain an edge in the form $u$ , $v$ , meaning vertex $u$ and vertex $v$ of the tree are connected by an edge.

Output

Print the maximum number of possible warps on the first line.

Constraints

$2 \le N \le 500$ $1 \le u, v \le N$

Examples3

Example 1
Input
```
3
1 2
2 3
```
Expected output
```
2
```
Example 2
Input
```
4
1 2
1 4
2 3
```
Expected output
```
4
```
Example 3
Input
```
4
1 2
2 3
2 4
```
Expected output
```
3
```