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<bits/stdc++.h>
using namespace std;
int n,m,head[100100],cnt,col[100100],tot[3],TE;
typedef long long ll;
ll res;
struct node{
	int to,next,val;
}edge[200100];
void ae(int u,int v){
	edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=1,head[u]=cnt++;
	edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=-1,head[v]=cnt++;
}
bool Dye(int x){
	tot[col[x]]++;
	bool ret=true;
	for(int i=head[x];i!=-1;i=edge[i].next){
		TE+=(edge[i].val==1);
		if(col[edge[i].to]==-1){
			col[edge[i].to]=(col[x]+edge[i].val+3)%3;
			ret&=Dye(edge[i].to);
		}
		else ret&=(col[edge[i].to]==(col[x]+edge[i].val+3)%3);
	}
	return ret;
}
int main(){
	scanf("%d%d",&n,&m),memset(head,-1,sizeof(head)),memset(col,-1,sizeof(col));
	for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),ae(x,y);
	for(int i=1;i<=n;i++){
		if(col[i]!=-1)continue;
		memset(tot,0,sizeof(tot)),TE=0;
		col[i]=0;
		if(!Dye(i)){res+=1ll*(tot[0]+tot[1]+tot[2])*(tot[0]+tot[1]+tot[2]);continue;}
		if(!tot[0]||!tot[1]||!tot[2]){res+=TE;continue;}
		res+=1ll*tot[0]*tot[1]+1ll*tot[1]*tot[2]+1ll*tot[2]*tot[0];
	}
	printf("%lld\n",res);
	return 0;
}