Contest Duration: ~ (local time) (130 minutes) Back to Home
F - Blackout /

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

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

• ある 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.