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>
#include <cstring>
#define MAXN 1000010
#define LL long long

struct edge{
	int to,next;
	edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n,m;
int g[MAXN],nume;
int p[MAXN][5],nump;
int e2[MAXN][2];
int f[MAXN],visit[MAXN];
int cnt[MAXN];

void addEdge(int u,int v){
	e[nume]=edge(v,g[u]);
	g[u]=nume++;
	e[nume]=edge(u,g[v]);
	g[v]=nume++;
}

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

void dfs(int x){
	visit[x]=1;
	for(int i=g[x];~i;i=e[i].next)
		if(!visit[e[i].to]){
			f[getf(e[i].to)]=getf(x);
			dfs(e[i].to);
		}
}

int main(){
#ifdef DEBUG
	freopen("F.in","r",stdin);
#endif
	memset(g,-1,sizeof g);
	scanf("%d%d",&n,&m);
	for(int j=0;j<5;j++)
		for(int i=1;i<=n;i++) 
			p[i][j]=++nump;
	for(int i=1;i<=nump;i++) f[i]=i;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&e2[i][0],&e2[i][1]);
		int u=e2[i][0],v=e2[i][1];
		addEdge(p[u][0],p[v][1]);
		addEdge(p[u][1],p[v][2]);
		addEdge(p[u][2],p[v][0]);
		addEdge(p[u][2],p[v][4]);
		addEdge(p[u][3],p[v][2]);
		addEdge(p[u][4],p[v][3]);
	}
	for(int i=1;i<=nump;i++)
		if(!visit[i])
			dfs(i);
	for(int i=1;i<=n;i++) cnt[getf(p[i][3])]++;
	LL ans=0;
	for(int i=1;i<=n;i++)
		ans+=cnt[getf(p[i][0])];
	for(int i=1;i<=m;i++)
		if(getf(p[e2[i][0]][0])!=getf(p[e2[i][1]][3]))
			ans++;
	printf("%lld\n",ans);
}