Y

Time limit1.5sMemory limit1024 MB

Summary

From a given tree, delete any vertices to leave the largest subtree shaped like a Y: three leaf paths meeting at one center, with no vertex of degree 4 or more.

Level: Hard8 of 10
Topics: Tree, DFS, Dynamic programming, Greedy
Solved: No attempts yet

Problem

A Y-tree is a tree that satisfies all of the following conditions.

No vertex is adjacent to $4$ or more vertices.
There is exactly one vertex adjacent to $3$ vertices.
There are exactly three vertices adjacent to exactly one vertex.

The size of a Y-tree is the number of vertices that form it.

You are given a tree with $N$ vertices numbered $1$ , $2$ , …, $N$ , one number per vertex. Write a program that finds the size of the largest Y-tree that can be obtained by deleting zero or more vertices from the given tree.

Input

The first line gives the integer $N$ , the number of vertices in the tree. ( $2 \leq N \leq 100\,000$ )

The next $N-1$ lines each give two integers $u$ and $v$ describing an edge of the tree. This means there is an edge connecting vertex $u$ and vertex $v$ . ( $1 \leq u, v \leq N$ , $u \neq v$ )

Every edge of the tree is given exactly once.

Output

On the first line, print the size of the largest Y-tree that can be made from the given tree.

If no Y-tree can be made, print $0$ .

Examples2

Example 1
Input
```
8
1 2
1 3
2 4
1 5
2 6
2 7
8 7
```
Expected output
```
6
```
Example 2
Input
```
3
1 2
2 3
```
Expected output
```
0
```