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 siz=1e6+1;
struct edge{
	int v,w,nxt;
}e[siz];

int n,m;
ll ans,cnt,_cnt;
ll ccnt[3];
int col[siz],head[siz];
bool flag;
bitset<siz> vis;

inline
int posi(int x){return ((x%3)+3)%3;}

void dfs(int now);
void add_edge(int u,int v,int w);

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,1);
		add_edge(v,u,-1);
	}
	for(int i=1;i<=n;i++){
		if(vis[i])
			continue;
		memset(ccnt,0,sizeof ccnt);
		_cnt=cnt=0;
		flag=false;
		dfs(i);
		if(flag)
			ans+=cnt*cnt;
		else
			if(ccnt[0]>0&&ccnt[1]>0&&ccnt[2]>0)
				ans+=ccnt[0]*ccnt[1]+ccnt[1]*ccnt[2]+ccnt[0]*ccnt[2];
			else
				ans+=_cnt;
	}
	printf("%lld\n",ans);
}

void dfs(int now)
{
	cnt++;
	vis[now]=true;
	ccnt[col[now]]++;
	for(int i=head[now];i!=0;i=e[i].nxt){
		if(e[i].w==1)
			_cnt++;
		if(!vis[e[i].v]){
			col[e[i].v]=posi(col[now]+e[i].w);
			dfs(e[i].v);
		}
		else
			if(col[e[i].v]!=posi(col[now]+e[i].w))
				flag=true;
	}
}

void add_edge(int u,int v,int w)
{
	static int cnt;
	e[++cnt]={v,w,head[u]};
	head[u]=cnt;
}