[AGC006F] Blackout

## 题目描述 我们有一个 $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 解释 很遗憾，没有任何白色格子能被涂黑。

[problemUrl]: https://atcoder.jp/contests/agc006/tasks/agc006_f 縦、横ともに $ 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 $

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

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 新たにマスを黒く塗ることができません。