/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1700 点
問題文
縦、横ともに 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) を黒く塗る。
すぬけ君が可能な限りマスを黒く塗ったとき、最終的に黒いマスは何個になるかを求めてください。
制約
- 1≤N≤10^5
- 1≤M≤10^5
- 1≤a_i,b_i≤N
- (a_i, b_i) はすべて相異なる。
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 a_2 b_2 : a_M b_M
出力
すぬけ君が可能な限りマスを黒く塗ったとき、最終的に黒いマスは何個になるかを出力せよ。
入力例 1
3 2 1 2 2 3
出力例 1
3
次のようにマスを黒く塗っていくことができます。
- マス (1, 2), (2, 3) がともに黒で、マス (3, 1) が白なので、マス (3, 1) を黒く塗る。
入力例 2
2 2 1 1 1 2
出力例 2
4
次のようにマスを黒く塗っていくことができます。
- マス (1, 1), (1, 2) がともに黒で、マス (2, 1) が白なので、マス (2, 1) を黒く塗る。
- マス (2, 1), (1, 2) がともに黒で、マス (2, 2) が白なので、マス (2, 2) を黒く塗る。
入力例 3
4 3 1 2 1 3 4 4
出力例 3
3
新たにマスを黒く塗ることができません。
Score : 1700 points
Problem Statement
We have a grid with N rows and N columns. The cell at the i-th row and j-th column is denoted (i, j).
Initially, M of the cells are painted black, and all other cells are white. Specifically, the cells (a_1, b_1), (a_2, b_2), ..., (a_M, b_M) are painted black.
Snuke will try to paint as many white cells black as possible, according to the following rule:
- If two cells (x, y) and (y, z) are both black and a cell (z, x) is white for integers 1≤x,y,z≤N, paint the cell (z, x) black.
Find the number of black cells when no more white cells can be painted black.
Constraints
- 1≤N≤10^5
- 1≤M≤10^5
- 1≤a_i,b_i≤N
- All pairs (a_i, b_i) are distinct.
Input
The input is given from Standard Input in the following format:
N M a_1 b_1 a_2 b_2 : a_M b_M
Output
Print the number of black cells when no more white cells can be painted black.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
3
It is possible to paint one white cell black, as follows:
- Since cells (1, 2) and (2, 3) are both black and a cell (3, 1) is white, paint the cell (3, 1) black.
Sample Input 2
2 2 1 1 1 2
Sample Output 2
4
It is possible to paint two white cells black, as follows:
- Since cells (1, 1) and (1, 2) are both black and a cell (2, 1) is white, paint the cell (2, 1) black.
- Since cells (2, 1) and (1, 2) are both black and a cell (2, 2) is white, paint the cell (2, 2) black.
Sample Input 3
4 3 1 2 1 3 4 4
Sample Output 3
3
No white cells can be painted black.