← 返回题目列表

Codeforces · 23/E

E. 树

中文机器翻译题面 查看原题

最近鲍勃发明了一种新的树游戏(我们应该提醒你,树是一个没有循环的连通图):他删除树的任何(可能是零)数量的边,并计算删除后留下的连通分量的大小的乘积。你的任务是找出鲍勃在他的新游戏中对于给定的树可以得到的最大数字。

输入

第一个输入行包含整数 n (1 ≤ n ≤ 700) — 树中的顶点数量。接下来的 n - 1 行包含边的描述。每行包含一对顶点索引,由一条边 ai, bi (1 ≤ ai, bi ≤ n) 连接。保证输入中描述的图是一棵树。

输出

输出鲍勃删除树的一些边后可以获得的唯一数字 - 连接组件大小的最大乘积。

示例

输入 #1

5
1 2
2 3
3 4
4 5

输出 #1

6

输入 #2

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

输出 #2

18

输入 #3

3
1 2
1 3

输出 #3

3