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<iostream>
#include<cstring>
#include<cstdio>
#define N (100000+1000)
using namespace std;

struct Edge{int to,next,len;}edge[N<<1];
int head[N],num_edge;
long long n,m,cnt[4],flag,col[N];
long long ans,sum,u,v;

void add(int u,int v,int l)
{
	edge[++num_edge].to=v;
	edge[num_edge].next=head[u];
	edge[num_edge].len=l;
	head[u]=num_edge;
}

void Dfs(int x)
{
	cnt[col[x]]++;
	for (int i=head[x]; i; i=edge[i].next)
	{
		if (edge[i].len==1) sum++;
		if (col[edge[i].to]==-1)
		{
			col[edge[i].to]=(col[x]+edge[i].len)%3;
			Dfs(edge[i].to);
		}
		else if (col[edge[i].to]!=(col[x]+edge[i].len)%3)
			flag=1;
	}
	
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for (int i=1; i<=m; ++i)
	{
		scanf("%lld%lld",&u,&v);
		add(u,v,1); add(v,u,2);
	}
	memset(col,-1,sizeof(col));
	for (int i=1; i<=n; ++i)
		if (col[i]==-1)
		{
			sum=cnt[0]=cnt[1]=cnt[2]=flag=0;
			col[i]=0; Dfs(i);
			if (flag)
			{
				long long t=cnt[0]+cnt[1]+cnt[2];
				ans+=t*t; continue;
			}
			if ((!cnt[0]) || (!cnt[1]) || (!cnt[2]))
			{
				ans+=sum;
				continue;
			}
			ans+=cnt[0]*cnt[1]+cnt[1]*cnt[2]+cnt[2]*cnt[0];
		}
	printf("%lld\n",ans);
}