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 <algorithm>
#include <cstdio>

using namespace std ;

typedef long long LL ;
const int N=2e6+10 ;

int to[N<<1] , nxt[N<<1] , dir[N<<1] , lst[N] ;
inline void add ( int u , int v )
{
	static int cnt=0 ;
	++cnt,to[cnt]=v,nxt[cnt]=lst[u],dir[cnt]=1,lst[u]=cnt,
	++cnt,to[cnt]=u,nxt[cnt]=lst[v],dir[cnt]=-1,lst[v]=cnt;
}

int n , m ;

int d[N] , c[N] , siz , fail , edge , cnt[3] ;
inline void Dfs ( int x )
{
	int i , y , C ;
	d[x]=1,++siz,cnt[c[x]]++;
	for ( i=lst[x],y=to[i] ; i ; i=nxt[i],y=to[i] )
	{
		C=(c[x]+3+dir[i])%3,
		edge+=(dir[i]==1);
		if ( !d[y] )
			c[y]=C,Dfs(y);
		else
			if ( c[y]!=C ) fail=1;
	}
	return ;
}

int main ()
{
	int i , u , v ;
	scanf("%d%d",&n,&m);
	for ( i=1 ; i<=m ; i++ )
		scanf("%d%d",&u,&v),
		add(u,v);
	LL res=0 ;
	for ( i=1 ; i<=n ; i++ )
		if ( !d[i] )
		{
			edge=siz=fail=cnt[0]=cnt[1]=cnt[2]=0;
			Dfs(i);
			if ( fail )
				res+=(LL)(siz)*(LL)(siz);
			else if ( !cnt[0] || !cnt[1] || !cnt[2] )
				res+=(LL)(edge);
			else
				res+=(LL)(cnt[0])*(LL)(cnt[1])
					+(LL)(cnt[1])*(LL)(cnt[2])
					+(LL)(cnt[2])*(LL)(cnt[0]);
		}
	printf("%lld\n",res);
	return 0 ;
}