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;
ll ans;
const int maxn=100005;
int n,m,i,j,t,k,s,head[maxn],N,poi,cnt[5],edgnt,col[maxn];
struct Edge
{
	int nxt,aim,len;
}edge[maxn*2];
inline void add_edge(int x,int y,int z)
{
	edge[++N]=(Edge){head[x],y,z};
	head[x]=N;
}
bool dfs(int x)
{
	bool ret=1;++poi;
	cnt[col[x]]++;
	for (int i=head[x];i;i=edge[i].nxt)
	{
		edgnt+=(edge[i].len==1);
		int des=edge[i].aim;
		if (col[des]!=-1)
		{
			if (col[des]==(col[x]+edge[i].len+3)%3) continue;
			ret=0;continue;
		}
		col[des]=(col[x]+edge[i].len+3)%3;
		if (!dfs(des)) ret=0;
	}
	return ret;
}
void work(int x)
{
	poi=0;col[x]=0;edgnt=0;
	cnt[0]=cnt[1]=cnt[2]=0;
	if (!dfs(x))
	{
		ans+=1ll*poi*poi;
		return;
	}
	if (cnt[0]&&cnt[1]&&cnt[2])
	 ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[0]*cnt[2]+1ll*cnt[1]*cnt[2];
	else ans+=1ll*edgnt;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d%d",&t,&k);
		add_edge(t,k,1);add_edge(k,t,-1);
	}
	memset(col,-1,sizeof(col));
	ans=0;
	for (i=1;i<=n;++i) if (col[i]==-1)
	{
		work(i);
	}
	printf("%lld\n",ans);
	return 0;
}