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<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N=100005;

int n,m,f[N],s[N],col[N],tot,t[3],cnt,last[N],nx[3]={1,2,0},ls[3]={2,0,1},flag;
bool vis[N];
struct edge{int to,next,op;}e[N*2];

int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int find(int x)
{
	if (f[x]==x) return x;
	else return f[x]=find(f[x]);
}

void addedge(int u,int v)
{
	e[++cnt].to=v;e[cnt].op=0;e[cnt].next=last[u];last[u]=cnt;
	e[++cnt].to=u;e[cnt].op=1;e[cnt].next=last[v];last[v]=cnt;
}

void dfs(int x)
{
	vis[x]=1;t[col[x]]++;tot++;
	for (int i=last[x];i;i=e[i].next)
		if (!vis[e[i].to]) col[e[i].to]=!e[i].op?nx[col[x]]:ls[col[x]],dfs(e[i].to);
		else if (col[e[i].to]!=(!e[i].op?nx[col[x]]:ls[col[x]])) flag=1;
}

int main()
{
	n=read();m=read();
	for (int i=1;i<=n;i++) f[i]=i;
	for (int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		addedge(x,y);
		if (find(x)!=find(y)) x=find(x),y=find(y),s[y]+=s[x],f[x]=y;
		s[find(x)]++;
	}
	LL ans=0;
	for (int i=1;i<=n;i++)
		if (!vis[i])
		{
			tot=t[0]=t[1]=t[2]=flag=0;
			dfs(i);
			if (flag) ans+=(LL)tot*tot;
			else if (t[0]&&t[1]&&t[2]) ans+=(LL)t[0]*t[1]+(LL)t[1]*t[2]+(LL)t[2]*t[0];
			else ans+=s[find(i)];
		}
	cout<<ans;
	return 0;
}