Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

For an undirected graph $G$ with $n$ nodes and $m$ edges, we can define the distance between $(i,j)$ ($\text{dist}(i,j)$) as the length of the shortest path between $i$ and $j$. The length of a path is equal to the number of the edges on it. Specially, if there are no path between $i$ and $j$, we make $\text{dist}(i,j)$ equal to $n$.

Then, we can define the weight of the graph $G$ ($w_G$) as $\sum_{i=1}^n \sum_{j=1}^n \text{dist}(i,j)$.

Now, Yuta has $n$ nodes, and he wants to choose no more than $m$ pairs of nodes $(i,j)(i \neq j)$ and then link edges between each pair. In this way, he can get an undirected graph $G$ with $n$ nodes and no more than $m$ edges.

Yuta wants to know the minimal value of $w_G$.

It is too difficult for Rikka. Can you help her?

In the sample, Yuta can choose $(1,2),(1,4),(2,4),(2,3),(3,4)$.

For an undirected graph $G$ with $n$ nodes and $m$ edges, we can define the distance between $(i,j)$ ($\text{dist}(i,j)$) as the length of the shortest path between $i$ and $j$. The length of a path is equal to the number of the edges on it. Specially, if there are no path between $i$ and $j$, we make $\text{dist}(i,j)$ equal to $n$.

Then, we can define the weight of the graph $G$ ($w_G$) as $\sum_{i=1}^n \sum_{j=1}^n \text{dist}(i,j)$.

Now, Yuta has $n$ nodes, and he wants to choose no more than $m$ pairs of nodes $(i,j)(i \neq j)$ and then link edges between each pair. In this way, he can get an undirected graph $G$ with $n$ nodes and no more than $m$ edges.

Yuta wants to know the minimal value of $w_G$.

It is too difficult for Rikka. Can you help her?

In the sample, Yuta can choose $(1,2),(1,4),(2,4),(2,3),(3,4)$.

提交代码