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 <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100005;
struct Edge{
	int to,next,w;
}e[MAXN<<1];
int head[MAXN],n,m,cnt;
inline void insert(int u,int v)
{
	e[++cnt].to=v,e[cnt].next=head[u],head[u]=cnt,e[cnt].w=1;
	e[++cnt].to=u,e[cnt].next=head[v],head[v]=cnt,e[cnt].w=2;
}
int mark[MAXN],sz,ecnt;
bool succ;
int t[5];
void dfs(int x)
{
	++t[mark[x]];
	++sz;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].to;
		++ecnt;
		if(mark[v]==-1)mark[v]=(mark[x]+e[i].w)%3,dfs(v);
		else if(mark[v]!=(mark[x]+e[i].w)%3)succ=false;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		insert(u,v);
	}
	memset(mark,-1,sizeof(mark));
	long long ans=0;
	for(int i=1;i<=n;++i)
		if(mark[i]==-1){
			sz=0;
			succ=true;
			memset(t,0,sizeof(t));
			mark[i]=0;
			ecnt=0;
			dfs(i);
			if(!succ)ans+=(long long)sz*sz;
			else{
				int flag=1;
				for(int i=0;i<3;++i)flag&=bool(t[i]);
				if(flag){
					ans+=(long long)t[0]*t[2]+(long long)t[1]*t[0]+(long long)t[2]*t[1];
				}else ans+=ecnt/2;
			}
		}
	cout<<ans<<endl;
	return 0;
}