Blackout

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.

Examples

Input

3 2 1 2 2 3

Output

3

Input

2 2 1 1 1 2

Output

4

Input

4 3 1 2 1 3 4 4

Output

3

inputFormat

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

outputFormat

Output

Print the number of black cells when no more white cells can be painted black.

Examples

Input

3 2 1 2 2 3

Output

3

Input

2 2 1 1 1 2

Output

4

Input

4 3 1 2 1 3 4 4

Output

3

样例

2 2
1 1
1 2

4