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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 100010

using namespace std;
typedef long long llg;

int hd[maxn],nt[maxn<<1],to[maxn<<1],c[maxn<<1],tt;
int n,m,co[maxn],SIZ,cm,du[maxn];
bool vis[maxn],su;
llg ans,ci[3];

void dfs(int u){
	vis[u]=1; SIZ++; ci[co[u]]++; cm+=du[u];
	for(int i=hd[u],v;v=to[i],i;i=nt[i])
		if(!vis[v]) co[v]=(co[u]+c[i])%3,dfs(v);
		else if(co[v]!=(co[u]+c[i])%3) su=1;
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d %d",&x,&y);
		to[++tt]=y;nt[tt]=hd[x];hd[x]=tt;
		to[++tt]=x;nt[tt]=hd[y];hd[y]=tt;
		c[tt-1]=1; c[tt]=2; du[x]++,du[y]++;
	}
	for(int i=1,now;i<=n;i++)
		if(!vis[i]){
			dfs(i);
			if(su) ans+=1ll*SIZ*SIZ;
			else{
				now=(!ci[0])+(!ci[1])+(!ci[2]);
				if(!now) ans+=ci[0]*ci[1]+ci[1]*ci[2]+ci[2]*ci[0];
				else ans+=cm>>1;
			}
			ci[0]=ci[1]=ci[2]=0; SIZ=cm=0; su=0;
		}
	printf("%lld",ans);
	return 0;
}