如您所知,鲍勃的兄弟住在弗拉特兰。 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