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>
#include<algorithm>
#define N 100010
#define ll long long
using namespace std;
struct edge{int x, y, z, f, next;}a[N*2];
int n, m, x, y, l, p[N], flag[N], sum[10], ff, sum_m;
ll ans;
inline void add(int x, int y, int z){a[++l].x=x; a[l].y=y; a[l].z=z; a[l].f=0; a[l].next=p[x]; p[x]=l;}
inline void dfs(int x){
	sum[flag[x]]++;
	for(int i=p[x]; i; i=a[i].next)if(!a[i].f){
		sum_m++; a[i].f=a[i^1].f=1;
		if(flag[a[i].y]>=0){if(flag[a[i].y]!=(flag[x]+a[i].z+3)%3)ff=1;}
		else{flag[a[i].y]=(flag[x]+a[i].z+3)%3; dfs(a[i].y);}
	}
}
int main(){
	scanf("%d%d", &n, &m);
	l=1; memset(p, 0, sizeof(p));
	for(int i=1; i<=m; i++){scanf("%d%d", &x, &y); add(x, y, 1); add(y, x, -1);}
	for(int i=1; i<=n; i++)flag[i]=-1;
	ans=0;
	for(int i=1; i<=n; i++)if(flag[i]==-1){
		sum[0]=sum[1]=sum[2]=ff=sum_m=0;
		flag[i]=0; dfs(i);
		if(ff){x=sum[0]+sum[1]+sum[2]; ans+=(ll)x*x; continue;}
		if(!sum[0]||!sum[1]||!sum[2])ans+=sum_m;
		else ans+=(ll)sum[0]*sum[1]+(ll)sum[1]*sum[2]+(ll)sum[2]*sum[0];
	}
	printf("%lld", ans);
	return 0;
}