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 <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 5e5 + 9;

int n, m; 
ll to[N << 1], nxt[N << 1], beg[N], tot;
ll c[N], w[N << 1];
ll ans, f[4], flag;

inline void _read(int &x)
{
	x = 0;
	char t = getchar();
	while (!isdigit(t)) t = getchar();
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar();
	}
}

inline void add(const int &u, const int &v, const int &c)
{
	to[++tot] = v;
	nxt[tot] = beg[u];
	w[tot] = c;
	beg[u] = tot;
}

inline void dfs(int u)
{
	f[c[u]]++;
	for (register int i = beg[u]; i; i = nxt[i])
	{
		if (w[i] == 1)f[3]++;
		if (!(~c[to[i]]))
		{
			c[to[i]] = (c[u] + w[i]) % 3;
			dfs(to[i]);
		}
		else if (c[to[i]] != (c[u] + w[i]) % 3)
			flag = 1;
	}
}

int main()
{
	_read(n), _read(m);
	for (register int i = 1, u, v; i <= m; i++)
	{
		_read(u), _read(v);
		add(u, v, 1), add(v, u, 2);
	}

	memset(c, -1, sizeof c);
	for (register int i = 1; i <= n; i++)
		if (!(~c[i]))
		{
			f[c[i] = 0] = f[1] = f[2] = f[3] = flag = 0;
			dfs(i);
			if (flag)
			{
				register ll cnt = f[0] + f[1] + f[2];
				ans += cnt * cnt;
				continue;
			}
			if ((!f[0]) || (!f[1]) || (!f[2]))
			{
				ans += f[3];
				continue;
			}

			ans += f[0] * f[1];
			ans += f[1] * f[2];
			ans += f[2] * f[0];
		}

	printf("%lld", ans);
	return 0;
}