ACM-ICPC-OJ训练营

s 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) (

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

dist(i,j) equal to

n.

Then, we can define the weight of the graph

G (

wG) as

∑ni=1∑nj=1dist(i,j).

Now, Yuta has

n nodes, and he wants to choose no more than

m pairs of nodes

(i,j)(i≠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

wG.

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).

The first line contains a number

t(1≤t≤10), the number of the testcases.

For each testcase, the first line contains two numbers

n,m(1≤n≤106,1≤m≤1012).

For each testcase, print a single line with a single number -- the answer.

1838: Rikka with Graph

题目描述

输入描述

输出描述

样例输入

样例输出

来源