配点 : $1700$ 点

問題文

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

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

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

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

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

制約

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

入力

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

$N$ $M$

$a_1$ $b_1$

$a_2$ $b_2$

$:$

$a_M$ $b_M$

出力

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

3 2
1 2
2 3

3

次のようにマスを黒く塗っていくことができます。

• マス ($1$, $2$), ($2$, $3$) がともに黒で、マス ($3$, $1$) が白なので、マス ($3$, $1$) を黒く塗る。

2 2
1 1
1 2

4

次のようにマスを黒く塗っていくことができます。

• マス ($1$, $1$), ($1$, $2$) がともに黒で、マス ($2$, $1$) が白なので、マス ($2$, $1$) を黒く塗る。
• マス ($2$, $1$), ($1$, $2$) がともに黒で、マス ($2$, $2$) が白なので、マス ($2$, $2$) を黒く塗る。

4 3
1 2
1 3
4 4

3

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