← 返回题目列表

Codeforces · 14/D

D. 两条路径

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

如您所知,鲍勃的兄弟住在弗拉特兰。 Flatland 有 n 个城市,由 n - 1 条双向道路连接。城市编号为 1 到 n。您可以沿着道路从一个城市前往另一个城市。

鲍勃的兄弟工作的“双路”公司赢得了修复弗拉特兰两条路的招标。路径是由道路顺序连接的一系列不同城市。允许公司自行选择修复路径。他们必须满足的唯一条件是两条路径不应该交叉(即不应该有共同的城市)。

众所周知,“双路径”公司将获得的利润等于两条路径长度的乘积。我们假设每条道路的长度等于 1,并且一条路径的长度等于其中的道路数量。找出公司可能获得的最大利润。

输入

第一行包含一个整数 n (2 ≤ n ≤ 200),其中 n 是该国城市的数量。接下来的 n - 1 行包含有关道路的信息。每行包含一对城市编号,通过道路 ai、bi (1 ≤ ai, bi ≤ n) 连接。

输出

输出最大可能的利润。

示例

输入 #1

4
1 2
2 3
3 4

输出 #1

1

输入 #2

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

输出 #2

0

输入 #3

6
1 2
2 3
2 4
5 4
6 4

输出 #3

4