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>
typedef unsigned ui;
constexpr ui N(1e5+11),M(N<<1);
ui head[N],to[M],nxt[M],e_cnt;
void addedge(ui u,ui v)
{
	to[++e_cnt]=v;
	nxt[e_cnt]=head[u];
	head[u]=e_cnt;
	return;
}
ui col[N],cnt[4];
bool DFS(ui u)
{
	++cnt[col[u]];
	bool ans(true);
	for(unsigned e(head[u]),v(to[e]);e;v=to[e=nxt[e]])
	{
		cnt[3]+=e&1;
		if(~col[v])
			ans&=e&1?(col[u]+1)%3==col[v]:(col[v]+1)%3==col[u];
		else
		{
			col[v]=(col[u]+(e&1?1:2))%3;
			ans&=DFS(v);
		}
	}
	return ans;
}
signed main(void)
{
	ui n,m;
	scanf("%u%u",&n,&m);
	for(ui u,v;m;--m)
	{
		scanf("%u%u",&u,&v);
		addedge(u,v);
		addedge(v,u);
	}
	long long unsigned ans(0);
	memset(col,255,sizeof(col));
	for(ui i(1);i<=n;++i)
		if(!~col[i])
		{
			col[i]=cnt[0]=cnt[1]=cnt[2]=cnt[3]=0;
			if(DFS(i))
				ans+=!cnt[0]||!cnt[1]||!cnt[2]?cnt[3]:1llu*cnt[0]*cnt[1]+1llu*cnt[1]*cnt[2]+1llu*cnt[2]*cnt[0];
			else
				ans+=1llu*(cnt[0]+cnt[1]+cnt[2])*(cnt[0]+cnt[1]+cnt[2]);
		}
	printf("%llu\n",ans);
	return 0;
}