题目描述

縦、横ともに $N$ マスのマス目があります。 上から $i$ マス目、左から $j$ マス目のマスを ($i$, $j$) と表します。

最初、$M$ 個のマスが黒く塗られており、それ以外のマスはすべて白です。 具体的には、マス ($a_1$, $b_1$), ($a_2$, $b_2$), $...$, ($a_M$, $b_M$) が黒く塗られています。

すぬけ君は次のルールに従い、可能な限りマスを黒く塗っていきます。

• ある $1\ <\ =x,y,z\ <\ =N$ について、マス ($x$, $y$), ($y$, $z$) がともに黒で、マス ($z$, $x$) が白ならば、マス ($z$, $x$) を黒く塗る。

すぬけ君が可能な限りマスを黒く塗ったとき、最終的に黒いマスは何個になるかを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_M$ $b_M$

输出格式

すぬけ君が可能な限りマスを黒く塗ったとき、最終的に黒いマスは何個になるかを出力せよ。

题目大意

题目描述

我们有一个 $N$ 行 $N$ 列的矩阵。第 $i$ 行第 $j$ 列的格子表示为 $(i,j)$。

开始时，有 $M$ 个格子是黑色，其他格子都是白色。特别地，开始时格子 $(a_{1},b_{1}),(a_{2},b_{2}),\cdots, (a_{M},b_{M})$ 是黑色。

スヌケ君会按照以下的规则尽可能多的将白色格子涂成黑色：

• 对于整数 $1\le x,y,z\le N$，如果 $(x,y)$ 和 $(y,z)$ 都是黑色，那么就把 $(z,x)$ 涂黑。

请计算出当再也没有白色格子能被涂黑时，黑色格子的个数。

说明

• $1\le N \le 10^{5}$
• $1\le M \le 10^{5}$
• $1\le a_{i},b_{i} \le N$
• 各黑格坐标互不相同

输入输出格式

输入格式

从标准输入输入，格式见下：

第一行包含两个整数 $N$ 和 $M$；

从第二行开始的 $M$ 行，每行有两个以空格隔开的整数 $a_{i}$ 和 $b_{i}$，表示第 $i$ 个黑色格子的坐标。

输出格式

输出一个整数到标准输出，表示当スヌケ君尽可能多的把格子涂黑之后，黑色格子的个数。

样例解释

样例 1 解释

可以按这样的方法涂黑一个格子：

• 因为格子 $(1,2)$ 和 $(2,3)$ 都是黑色而 $(3,1)$ 是白色，把 $(3,1)$ 涂黑。

样例 2 解释

可以按这样的方法涂黑两个格子：

• 因为格子 $(1,1)$ 和 $(1,2)$ 都是黑色而 $(2,1)$ 是白色，把 $(2,1)$ 涂黑。

• 因为格子 $(2,1)$ 和 $(1,2)$ 都是黑色而 $(2,2)$ 是白色，把 $(2,2)$ 涂黑。

样例 3 解释

很遗憾，没有任何白色格子能被涂黑。

3 2
1 2
2 3

3

2 2
1 1
1 2

4

4 3
1 2
1 3
4 4

3

提示

制約

• $1\ <\ =N\ <\ =10^5$
• $1\ <\ =M\ <\ =10^5$
• $1\ <\ =a_i,b_i\ <\ =N$
• ($a_i$, $b_i$) はすべて相異なる。

Sample Explanation 1

次のようにマスを黒く塗っていくことができます。 - マス ($1$, $2$), ($2$, $3$) がともに黒で、マス ($3$, $1$) が白なので、マス ($3$, $1$) を黒く塗る。

Sample Explanation 2

次のようにマスを黒く塗っていくことができます。 - マス ($1$, $1$), ($1$, $2$) がともに黒で、マス ($2$, $1$) が白なので、マス ($2$, $1$) を黒く塗る。 - マス ($2$, $1$), ($1$, $2$) がともに黒で、マス ($2$, $2$) が白なので、マス ($2$, $2$) を黒く塗る。

Sample Explanation 3

新たにマスを黒く塗ることができません。