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> 
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
typedef long long ll;
using namespace std;
inline int read(){
	int n=0,f=1;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if (c=='-') c=getchar(),f=-1;
	for(;c>='0'&&c<='9';c=getchar()) n=n*10+c-48;
	return n*f;
}
const int maxn=1e5+5;
int i,j,n,m,k[maxn],ne[maxn],g[maxn],num;
int k1[maxn],ne1[maxn],g1[maxn],cnt,num1;
int d[maxn];
bool bz[maxn],bk;ll ans,s[3],size;
void add(int x,int y){
	ne[++num]=k[x],k[x]=num,g[num]=y;
	ne1[++num1]=k1[y],k1[y]=num1,g1[num1]=x;
}
void dfs(int x,int y){
	int i;
	bz[x]=1,s[d[x]=y]++;
	y=(y+1)%3;
	for(i=k[x];i;i=ne[i]){
		cnt++;
		int go=g[i];
		if (!bz[go]) dfs(go,y);else bk|=d[go]!=y; 
	}
	y=(y+1)%3;
	for(i=k1[x];i;i=ne1[i]){
		int go=g1[i];
		if (!bz[go]) dfs(go,y);else bk|=d[go]!=y; 
	}
}
int main(){
	n=read(),m=read();
	fo(i,1,m) {
		int x=read(),y=read();
		add(x,y);
	}num=0;
	fo(i,1,n) if (!bz[i]) {
		cnt=bk=s[0]=s[1]=s[2]=0,dfs(i,0);
		if (bk) {
			size=s[0]+s[1]+s[2],ans+=size*size;continue;
		}
		if (!s[0]||!s[1]||!s[2]){
			ans+=cnt;continue;
		}
		ans+=s[0]*s[1]+s[1]*s[2]+s[2]*s[0];
	}
	printf("%lld\n",ans);
}