Background

L invented a game related to trees.

Problem Description

He deletes any number (possibly $0$) of edges from the tree and computes the product of the sizes of all connected components after the deletions. L scores that many points. Your task is, for a given tree, to find the maximum score L can obtain.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.

The next $(n-1)$ lines each contain two integers $u, v$, indicating that there is an edge connecting $u$ and $v$.

Output Format

Output a single integer, the maximum score L can obtain.

5
1 2
2 3
3 4
4 5

6

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

18

3
1 2
1 3 

3 

Hint

Constraints

• For $10\%$ of the testdata, $n \leq 5$.
• For $30\%$ of the testdata, $n \leq 100$.
• For another $30\%$ of the testdata, the given tree is a path.
• For $100\%$ of the testdata, $1 \leq n \leq 700$, $1 \leq u, v \leq n$.

Translated by ChatGPT 5