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 Rint register int
#define C(n,m) (n<m?0:1ll*fac[n]*invfac[n-m]%mod*invfac[m]%mod)
using namespace std;
int T,n,m,p,k,head[100010],o=0,sz,ed,cnt[3],c[100010];
bool can,vis[100010];
struct edge{
	int to,link,w;
}e[200010];
void add_edge(int u,int v){
	e[++o].to=v,e[o].link=head[u],head[u]=o,e[o].w=1;
	e[++o].to=u,e[o].link=head[v],head[v]=o,e[o].w=2;
}
void dfs(int u,int col){
	cnt[col]++;vis[u]=true;c[u]=col,sz++;
	for(int i=head[u];i;i=e[i].link){
		if(e[i].w==1) ed++;
		if(vis[e[i].to]){
			if(c[e[i].to]!=(col+e[i].w)%3) can=false;
			continue;
		}
		dfs(e[i].to,(col+e[i].w)%3);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),add_edge(u,v);
	long long ans=0;
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		sz=ed=cnt[0]=cnt[1]=cnt[2]=0;can=true;
		dfs(i,0);
		if(!can) ans+=1ll*sz*sz;
		else{
			if(!min(min(cnt[0],cnt[1]),cnt[2])) ans+=ed;
			else ans+=1ll*cnt[0]*cnt[2]+1ll*cnt[0]*cnt[1]+1ll*cnt[1]*cnt[2];
		}
	}
	printf("%lld\n",ans); 
}