AtCoder Grand Contest 006

F - Blackout


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 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.


Submit提出する