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;
#define N 1111116
#define next nxt

int n,m,x[N],y[N],z[N],w[N],next[N],p[N],h[N][3];
long long cnt,cmt,c[3],ans;

void travel(int x,int k){
	if (!h[x][0]&&!h[x][1]&&!h[x][2]) cnt++;
	h[x][k]=1;c[k]++;
	for (int t=p[x];t;t=next[t]){
		if (!w[t]) cmt++;w[t]=1;
		if (!h[y[t]][(k+z[t])%3])
		travel(y[t],(k+z[t])%3);
	}
}

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();m=read();
	for (int i=1;i<=m;i++){
		x[2*i-1]=y[2*i]=read();
		y[2*i-1]=x[2*i]=read();
		z[2*i-1]=1;z[2*i]=2;
		next[2*i-1]=p[x[2*i-1]];p[x[2*i-1]]=2*i-1;
		next[2*i]=p[x[2*i]];p[x[2*i]]=2*i;
	}
	for (int i=1;i<=n;i++)
		if (!h[i][0]&&!h[i][1]&&!h[i][2]){
			cnt=0;cmt=0;c[0]=c[1]=c[2]=0;travel(i,0);
			if (h[i][1]) ans+=cnt*cnt;
			else if (c[1]&&c[2]) ans+=c[0]*c[1]+c[1]*c[2]+c[2]*c[0];
			else ans+=cmt/2;
		}
	printf("%lld\n",ans);
	return 0;
}