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 pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
typedef vector<int> vec;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
bool gg;
int E,nxt[500010],hed[500010],P,Q,nedge,too[500010],val[500010],d[500010],n,m,x,y,cnt[3];
LL ans;
void ae(int x,int y,int w){
	nxt[++nedge]=hed[x];
	hed[x]=nedge;
	too[nedge]=y;
	val[nedge]=w;
}
void dfs(int x,int D){
	++cnt[D];
	d[x]=D;
	for (int i=hed[x];i;i=nxt[i]){
		int y=too[i];
		++E;
		if (d[y]==-1) dfs(y,(D+val[i]+3)%3);
		if ((D+val[i]+3)%3!=d[y]) gg=1;
	}
}
int main(){
	cin>>n>>m;
	FOR(i,1,m){
		getint(x),getint(y);
		ae(x,y,1),ae(y,x,-1);
	}
	memset(d,-1,sizeof(d));
	FOR(rp,1,n) if (d[rp]==-1){
		cnt[0]=cnt[1]=cnt[2]=0;
		gg=0;
		E=0;
		dfs(rp,0);
		if (gg) ans+=1ll*(cnt[0]+cnt[1]+cnt[2])*(cnt[0]+cnt[1]+cnt[2]);
		else if (!cnt[0] || !cnt[1] || !cnt[2]) ans+=E/2;
		else ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[1]*cnt[2]+1ll*cnt[2]*cnt[0];
	}
	cout<<ans<<endl;
	return 0;
}