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;
typedef long long ll;
const int N=1e5+10;
int n,m,head[N],nxt[N*2],to[N*2],num=0,c[N],E=0,a[4],dis[N*2];
bool flag=0,vis[N*2];
vector<int>S;
inline void link(int x,int y,int z){
	nxt[++num]=head[x];to[num]=y;head[x]=num;dis[num]=z;}
inline void dfs(int x){
	S.push_back(x);
	for(int i=head[x];i;i=nxt[i]){
		int u=to[i],t=c[x]+dis[i];
		if(!vis[i])vis[i]=1,E++;
		if(!t)t=3;if(t==4)t=1;
		if(c[u]){
			if(c[u]!=t)flag=1;
		}
		else c[u]=t,dfs(u);
	}
}
int main(){
	int x,y;ll ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		link(x,y,1);link(y,x,-1);
	}
	for(int i=1;i<=n;i++){
		if(!c[i]){
			vector<int>().swap(S);c[i]=1;flag=0;E=0;
			dfs(i);
			memset(a,0,sizeof(a));
			for(int j=S.size()-1;j>=0;j--)a[c[S[j]]]++;
			if(flag)ans+=(ll)S.size()*S.size();
			else if(!a[1] || !a[2] || !a[3])ans+=E/2;
			else ans+=1ll*a[1]*a[2]+1ll*a[2]*a[3]+1ll*a[1]*a[3];
		}
	}
	cout<<ans<<endl;
	return 0;
}