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>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 100005;

int n, m, tot, cnt[3], col[MAXN];
vector <pii> adj[MAXN];
bool flg;
LL ans;

inline void Dfs(int x)
{
	cnt[col[x]] ++;
	tot += adj[x].size();
	for (auto e : adj[x])
		if (!~col[e.xx])
			col[e.xx] = (col[x] + e.yy) % 3, Dfs(e.xx);
		else if (col[e.xx] != (col[x] + e.yy) % 3)
			flg = true;
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read(), m = Read(), mset(col, -1);
	for (int i = 1, x, y; i <= m; i ++)
		x = Read(), y = Read(), adj[x].pb(mp(y, 1)), adj[y].pb(mp(x, 2));
	for (int i = 1; i <= n; i ++)
		if (!~col[i])
		{
			col[i] = tot = cnt[0] = cnt[1] = cnt[2] = flg = 0, Dfs(i);
			if (flg)
				ans += 1LL * (cnt[0] + cnt[1] + cnt[2]) * (cnt[0] + cnt[1] + cnt[2]);
			else if (!cnt[0] || !cnt[1] || !cnt[2])
				ans += tot >> 1;
			else
				ans += 1LL * cnt[0] * cnt[1] + 1LL * cnt[1] * cnt[2] + 1LL * cnt[2] * cnt[0];
		}
	return printf("%lld\n", ans), 0;
}