33095번 - Independent Set (Max) 다국어

문제

You are given a tree of $N$ nodes (numbered from 1ドル$ to $N$). The edges are numbered from 1ドル$ to $N - 1$; edge $i$ connects node $U_i$ and $V_i$.

A non-empty set of nodes is independent if none of the nodes in the set are adjacent to each other. The following illustration provides an example of sets which are independent, and sets which are not. The nodes colored in red are the members of the set.

The score of an independent set can be calculated as the product of:

• the number of nodes in the set, and
• the minimum number of edges such that all nodes in the set are still connected.

The following illustration provides an example for calculating the score of an independent set. There are 2ドル$ nodes in the set. The minimum number of edges to connect all nodes in the set is 3ドル,ドル as shown by the edges colored in red. The score of this set is 2ドル \cdot 3 = 6$.

Note that the score of an independent set consisting of only 1ドル$ node is 0ドル$.

Determine the maximum score over all non-empty independent sets within the tree.

입력

The first line consists of an integer $N$ (2ドル ≤ N ≤ 100,円 000$).

Each of the next $N - 1$ lines consists two integers $U_i$ $V_i$ (1ドル ≤ U_i , V_i ≤ N$). The input edges form a tree.

출력

Output a single integer representing the maximum score over all non-empty independent sets within the tree.

제한

힌트