U656703 三角计数 / Triangle

小 P 一直觉得，三角形是世界上最安心的形状——三条边相互连接，稳稳的，永远不会坍塌。 今天，她的面前出现了 $n$ 个编号为 1 到 n 的点，以及 $m$ 条相互连接着节点的无向边。小 P 可以挑选 $m$ 条边中的任意条边，构成一个无向图。小 P 想数一数，在所有这些可能的图中，能形成多少个三角形——也就是三个点 $u, v, w$（其中 $u

因为小 P 的面前的点有点多，所以她会问你很多个问题…… 第一行一个整数 $t$，表示小 P 的问题数量。 接下来输入 $t$ 组数据，在每组数据中： 第一行两个整数 $n,m$，表示顶点数量和无向边数量。 接下来 $m$ 行，每行两个整数 $u,v$，表示 $u,v$ 间有一条无向边。

对于每组数据，输出一行一个整数，表示满足条件的三角形个数。

#### 样例解释 显然，当顶点数量只有 $2$ 个时，无论怎么选边，都是无法构成三角形的。 #### 数据范围 对于 $30\%$ 的数据，$n,m \leq 100$。 对于 $50\%$ 的数据，$n,m \leq 5000$。 对于 $70\%$ 的数据，$n,m \leq 5 \times 10^4$。 对于 $100\%$ 的数据，保证 $t \leq 10,n \leq 2 \times 10^5,m \leq \min(\frac{n(n-1)}{2},4 \times 10^5)$。不保证给定的图中无重边无自环。 idea：DWBbobo 题面：Deepseek