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;
const int maxn=2e5+999;

struct edge{
	int to,nxt,dis;
}e[maxn];
int head[maxn],tot;
void add(int x,int y,int z){
	e[++tot].to=y;
	e[tot].nxt=head[x];
	e[tot].dis=z;
	head[x]=tot;
}
int n,m,col[maxn],cnt0,cnt1,cnt2,cnt,fl;

void dfs(int x,int c){
	col[x]=c;
	if(c==0)cnt0++;
	if(c==1)cnt1++;
	if(c==2)cnt2++;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(e[i].dis>0)++cnt;
		if(col[y]==-1)dfs(y,(c+e[i].dis+3)%3);
		else if(col[y]!=(c+e[i].dis+3)%3)fl=1;
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y,1);add(y,x,-1);
	}
	long long ans=0;
	memset(col,-1,sizeof(col));
	for(int i=1;i<=n;++i){
		if(col[i]==-1){
			fl=cnt=cnt0=cnt1=cnt2=0;
			dfs(i,0);
			if(fl){//染色失败 完全图 
				ans+=1ll*(cnt0+cnt1+cnt2)*(cnt0+cnt1+cnt2);
			}
			else if(cnt0&&cnt1&&cnt2){
				ans+=1ll*cnt0*cnt1+1ll*cnt1*cnt2+1ll*cnt2*cnt0;
			}
			else ans+=cnt;
		}
	}
	cout<<ans;
}