Problem: 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

Solution (in CPP):

Solution:
#include <stdio.h>

int N,M,P[100100],C[100100],S[100100],E[100100];
long long U[100100][3];

int find(int x)
{
	if (P[x] != x){
		int c = C[x], p = P[x];
		P[x] = find(p);
		C[x] = (C[p] + c) % 3;
	}
	return P[x];
}

int main()
{
	scanf ("%d %d",&N,&M);
	for (int i=1;i<=N;i++) P[i] = i;
	for (int i=0;i<M;i++){
		int x,y;
		scanf ("%d %d",&x,&y);

		int X = find(x), Y = find(y);
		if (X == Y){
			if ((C[x] + 1) % 3 != C[y])
				S[X] = 1;
		}
		else{
			P[Y] = X;
			C[Y] = (C[x] - C[y] + 4) % 3;
			S[X] |= S[Y];
			E[X] += E[Y];
		}
		E[X]++;
	}

	for (int i=1;i<=N;i++){
		int x = find(i);
		U[x][C[i]]++;
	}

	long long ans = 0;
	for (int i=1;i<=N;i++) if (find(i) == i){
		if (S[i])
			ans += (U[i][0] + U[i][1] + U[i][2]) * (U[i][0] + U[i][1] + U[i][2]);
		else if (U[i][0] > 0 && U[i][1] > 0 && U[i][2] > 0)
			ans += U[i][0] * U[i][1] + U[i][1] * U[i][2] + U[i][2] * U[i][0];
		else
			ans += E[i];
	}

	printf ("%lld\n",ans);

	return 0;
}