3740. 对称变量

单点时限: 2.0 sec

内存限制: 512 MB

Cuber QQ 对多项式的研究造诣极高。

他曾自己定义过多项式中”对称变量”的概念。

对称变量指的是,在多项式中将这两个变量相互替换以后,多项式不会有任何变化。

例如多项式 $x_1x_2+x_1x_3+x_2x_3$ 中变量 $x_1$ 和 $x_2$ 相互替换后变为 $x_2x_1+x_2x_3+x_1x_3$ ,显然这两个多项式是等价的,于是我们就称在该多项式中变量 $x_1$ 和变量 $x_2$ 是一对对称变量。

现在 Cuber QQ 给出一个 $n$ 元二次多项式,其中有 $m$ 个二次项(由两个变量的乘积构成)且每一项的系数至多为 $1$ (即不会存在相同的项),可能存在平方项(两个相同变量的乘积)。

Cuber QQ 想知道在给定的多项式中有多少对变量是对称的。

输入格式

输入数据第一行包含一个整数 $T(1\le T\le 1000)$ ,表示数据组数。

对于每组数据,第一行包含两个整数 $n,m(1\le n,m \le 5\cdot 10^5)$ ,含义如体面所述。

接下来的 $m$ 行,每行两个整数 $i,j(1\le i,j\le n)$ 表示这一项是由 $x_ix_j$ 构成的。

保证 $1\le \sum n,\sum m \le 5\cdot 10^5$ 。

输出格式

对于每组数据,输出一行一个整数表示答案。

样例

Input
1
3 3
1 2
1 3
2 3
Output
3

23 人解决,46 人已尝试。

34 份提交通过,共有 357 份提交。

6.2 EMB 奖励。

创建: 4 年,9 月前.

修改: 4 年,9 月前.

最后提交: 2 年前.

来源: EOJ Monthly 2020.1

题目标签