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<cstdio>
using namespace std;
typedef long long LL;
const int N=100005;
struct node { int y,z,next; } a[N<<1];
LL an;
int s[3],head[N],z[N],i,j,k,n,m,S,E;
bool p[N],F;
char c;

inline char getc()
{
	#define VV 10000000
	static char s[VV],*l=s,*r=s;
	if (l==r)
		l=s,r=s+fread(s,1,VV,stdin);
	return l==r?0:*l++;
}

int read(){ int z=0; do c=getc(); while (c<'0'||c>'9'); while (c>='0'&&c<='9') z*=10,z+=c-'0',c=getc(); return z; }

void jb(int y,int x)
{
	a[++k]=(node){y,1,head[x]},head[x]=k,
	a[++k]=(node){x,2,head[y]},head[y]=k;
}

void dfs(int w)
{
	p[w]=1,++s[z[w]],++S;
	for (register int j=head[w];j;j=a[j].next)
	{
		int c=a[j].y;
		if (j&1) ++E;
		if (!p[c])
			z[c]=(z[w]+a[j].z)%3,dfs(c);
		else
			if (z[c]!=(z[w]+a[j].z)%3)
				F=0;
	}
}

int main()
{
	n=read(),m=read();
	while (m--) jb(read(),read());
	for (i=1;i<=n;++i)
		if (!p[i])
		{
			F=1,s[0]=s[1]=s[2]=S=E=0;
			dfs(i);
			if (F)
				if (s[0]&&s[1]&&s[2])
					an+=(LL)s[0]*s[1]+(LL)s[1]*s[2]+(LL)s[2]*s[0];
				else
					an+=E;
			else
				an+=(LL)S*S;
		}
	printf("%lld\n",an);
	return 0;
}