Bob's brother lives in France. There are n cities in France, and there are n-1 two-way roads connecting these cities. These cities are numbered from 1~n. You can follow these roads from one city to any other city.  
Bob's brother worked in the "two way" company and just got to repair any two paths in France. A path refers to the sequence of roads connecting two different cities. The company can independently choose the road to repair, the only condition is that the two paths can not be crossed (that is, there can be no common city).
Of course, we all know that there is profit, and the profit of "two paths" company will be equal to the product of the length of two paths. Suppose the length of each road is equal to 1, and the length of the path is equal to the number of roads. Please make the best profit for the company.

Retract

input

A single set of test data.
The first line is an integer n (2 less than n or less than 200), and N is the number of cities in this country.
Next, the n-1 row is the information of the road, each row is two integers ai,bi, they are the numbers of the city, indicating that there is a road directly connected between AI and bi. (1 < ai,bi < n).

output

Export maximum profit.

Code:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=200+10;
int G[maxn][maxn],vis[maxn];
int a[maxn],b[maxn];
int dist[maxn];
int index,maxx;
int n;
void BFS(int s)
{
    memset(vis,0,sizeof(vis));
    dist[s]=0;
    vis[s]=1;
    queue<int >Q;
    Q.push(s);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int i=1;i<=n;i++)
        {
            if(!G[u][i]) continue;
            if(vis[i]) continue;
            vis[i]=1;
            dist[i]=dist[u]+1;
            Q.push(i);
            if(maxx<dist[i])
            {
                maxx=dist[i];
                index=i;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        G[a[i]][b[i]]=1;
        G[b[i]][a[i]]=1;
    }
    int ans=0;
    for(int i=1;i<n;i++)
    {
        memset(dist,0,sizeof(dist));
        G[a[i]][b[i]]=0;
        G[b[i]][a[i]]=0;
        maxx=0,index=0;
        BFS(a[i]);
        BFS(index);
        int temp=maxx;

        memset(dist,0,sizeof(dist));
        maxx=0,index=0;
        BFS(b[i]);
        BFS(index);
        ans=max(ans,maxx*temp);
        G[a[i]][b[i]]=1;
        G[b[i]][a[i]]=1;
    }
    printf("%d\n",ans);
}