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 <cstdio>
long long O;
int N, M, f[100001], w[100001], s[100001][3], d[100001], e[100001];
int F(int x)
{
	if (f[x] == x)
		return x;
	F(f[x]);
	d[x] = (d[x] + d[f[x]]) % 3;
	return f[x] = f[f[x]];
}
void add(int u, int v)
{
	int fu = F(u), fv = F(v);
	if (fu == fv)
	{
		if (d[u] != (d[v] + 1) % 3)
			w[fu] = 1;
		e[fu]++;
	}
	else
	{
		f[fu] = fv;
		w[fv] |= w[fu];
		d[fu] = (4 + d[v] - d[u]) % 3;
		for (int i = 0; i < 3; i++)
			s[fv][(i + d[fu]) % 3] += s[fu][i];
		e[fv] += e[fu] + 1;
	}
}
int main()
{
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++)
	{
		f[i] = i;
		s[i][0] = 1;
	}
	while (M--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	for (int i = 1; i <= N; i++)
		if (F(i) == i)
		{
			if (w[i])
				O += (long long)(s[i][0] + s[i][1] + s[i][2]) * (s[i][0] + s[i][1] + s[i][2]);
			else if (s[i][0] && s[i][1] && s[i][2])
				O += (long long)s[i][0] * s[i][1] + (long long)s[i][1] * s[i][2] + (long long)s[i][2] * s[i][0];
			else
				O += e[i];
		}
	printf("%lld\n", O);
	return 0;
}