#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m;
struct edge{
	int to,lst;
}e[4000005];
int lst[1000005],tt=1;
vector<int>vec[1000005];
int siz[1000005],bel[1000005];
void add(int x,int y){
	e[++tt].to=y;
	e[tt].lst=lst[x];
	lst[x]=tt;
}
int dfn[1000005],low[1000005],tim,stk[1000005],tp,sz[1000005];
int cc;
void dfs(int now,int lt){
	low[now]=dfn[now]=++tim;
	stk[++tp]=now;
	for(int u=lst[now];u;u=e[u].lst){
		int to=e[u].to;
		if(!dfn[to])dfs(to,u),low[now]=min(low[now],low[to]);
		else if(u!=(lt^1))low[now]=min(low[now],dfn[to]);
	}
	if(low[now]==dfn[now]){
		cc++;
		while(tp>0){
			int u=stk[tp--];
			bel[u]=cc;siz[cc]++;
			if(now==u)break;
		}
	}
}
ll f[1000005],ans;
void solve(int now,int fa){
	sz[now]=siz[now];
	f[now]=0;
	for(auto to:vec[now]){
		if(to==fa)continue;
		solve(to,now);
		sz[now]+=sz[to];
	}
	for(auto to:vec[now]){
		if(to==fa)continue;
		f[now]=max(f[now],f[to]+(ll)(sz[now]-sz[to])*sz[to]);
	}
}
ll val[1000005];
struct line{
	ll k,b;
}line[1000005];
int ls[20000005],rs[20000005],best[20000005],rt,tot;
ll calc(int id,int x){
	return line[id].k*x+line[id].b;
}
void ins(int &p,int l,int r,int id){
	if(!p)p=++tot;
	int mid=l+r>>1;
	if(calc(id,mid)>calc(best[p],mid))swap(id,best[p]);
	if(l==r)return;
	if(calc(id,l)>calc(best[p],l))ins(ls[p],l,mid,id);
	if(calc(id,r)>calc(best[p],r))ins(rs[p],mid+1,r,id); 
}
ll Get(int p,int l,int r,int x){
	ll res=calc(best[p],x);
	if(l==r)return res;
	int mid=l+r>>1;
	if(x<=mid)res=max(res,Get(ls[p],l,mid,x));
	else res=max(res,Get(rs[p],mid+1,r,x));
	return res; 
}
void clr(){
	for(int i=1;i<=tot;i++)best[i]=ls[i]=rs[i]=0;
	tot=rt=0;
}
void change(int now,int fa){
	if(now!=1){
		int res=n-sz[now];
		f[now]=val[now]+(ll)(n-res)*res;
		for(auto to:vec[now]){
			if(to==fa)continue;
			f[now]=max(f[now],f[to]+(ll)(n-sz[to])*sz[to]);
		}
		for(auto to:vec[now])if(to!=fa)val[to]=val[now]+(ll)(sz[now]-sz[to])*res;
	}
	ans=max(ans,f[now]);
	clr();
	for(auto to:vec[now]){
		if(to==fa)continue;
		line[to].k=sz[to],line[to].b=f[to]-(ll)sz[to]*sz[to];
		val[to]=max(val[to],Get(rt,1,n,n-sz[to]));
		ins(rt,1,n,to);
	}
	reverse(vec[now].begin(),vec[now].end());
	clr();
	for(auto to:vec[now]){
		if(to==fa)continue;
		val[to]=max(val[to],Get(rt,1,n,n-sz[to]));
		ins(rt,1,n,to);
	}
	for(auto to:vec[now]){
		if(to==fa)continue;
		change(to,now);
	}
}
ll max_diversity(int N, int M, vector<int> U, vector<int> V){n=N,m=M;
	line[0].b=-1e18;
	for(int i=0;i<m;i++){
		int x=U[i],y=V[i];x++,y++;
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		for(int u=lst[i];u;u=e[u].lst){
			if(bel[i]!=bel[e[u].to])vec[bel[i]].push_back(bel[e[u].to]);
		}
	}
	solve(1,0);
	change(1,0);
	return ans;
}