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>
using namespace std;
typedef long long ll;
const int N=100100;
int i,j,k,n,m,ch,ff,x,y,Fg,En,cnt;
ll ans;
int nm[3],c[N],h[N];
struct edge { int s,n,v;} E[N<<1];
void R(int &x) {
	ff=x=0;ch=getchar();
	while (ch<'0' || '9'<ch) { if (ch=='-') ff=1;ch=getchar();}
	while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar();
	if (ff) x=-x;
}
void E_add(int x,int y) {
	E[++En].s=y;E[En].v=1;
	E[En].n=h[x];h[x]=En;
	E[++En].s=x;E[En].v=2;
	E[En].n=h[y];h[y]=En;
}
void dfs(int x) {
	nm[c[x]]++;
	for (int k=h[x];k;k=E[k].n) {
		cnt++;
		int nt=(c[x]+E[k].v)%3;
		if (c[E[k].s]==-1) {
			c[E[k].s]=nt;
			dfs(E[k].s);
		}
		else {
			if (c[E[k].s]!=nt) Fg=1;
		}
	}
}
int main() {
	R(n);R(m);
	for (i=1;i<=m;i++) {
		R(x);R(y);
		E_add(x,y);
	}
	memset(c,-1,sizeof c);
	for (i=1;i<=n;i++) if (c[i]==-1) {
		nm[0]=nm[1]=nm[2]=0;
		cnt=0;
		c[i]=0;
		Fg=0;
		dfs(i);
		cnt/=2;
		if (Fg) {
			int t=nm[0]+nm[1]+nm[2];
			ans+=(ll) t*t;
		}
		else {
			if (!nm[0] || !nm[1] || !nm[2]) ans+=cnt;
			else ans+=(ll) nm[0]*nm[1]+(ll) nm[1]*nm[2]+(ll) nm[2]*nm[0];
		}
	}
	printf("%lld\n",ans);
}