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<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100010;
const int maxM=maxN*2;
const int inf=2147483647;

int n,m;
int edgecnt=-1,Head[maxN],Next[maxM],V[maxM],W[maxM];
int Col[maxN];
bool getring;
ll edge,node;
bool vis[maxN];
ll Aper[3];

void Add_Edge(int u,int v,int w);
void dfs(int u,int col);

int main()
{
	ios::sync_with_stdio(false);mem(Head,-1);
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		int u,v;cin>>u>>v;Add_Edge(u,v,1);Add_Edge(v,u,2);
	}
	mem(Col,-1);
	ll Ans=0;
	for (int i=1;i<=n;i++)
		if (Col[i]==-1)
		{
			getring=0;edge=0;node=0;Aper[0]=Aper[1]=Aper[2]=0;
			dfs(i,0);
			//cout<<getring<<" "<<edge<<" "<<node<<" "<<Aper[0]<<" "<<Aper[1]<<" "<<Aper[2]<<endl;
			if (getring) Ans+=(ll)node*node;
			else if ((Aper[0]==0)||(Aper[1]==0)||(Aper[2]==0)) Ans+=edge;
			else Ans+=(ll)Aper[0]*Aper[1]+(ll)Aper[1]*Aper[2]+(ll)Aper[2]*Aper[0];
		}
	cout<<Ans<<endl;
	return 0;
}

void Add_Edge(int u,int v,int w)
{
	edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;
	return;
}

void dfs(int u,int col)
{
	if (Col[u]!=-1)
	{
		if (Col[u]!=col) getring=1;
		return;
	}
	
	Col[u]=col;Aper[col]++;node++;
	for (int i=Head[u];i!=-1;i=Next[i])
	{
		if (vis[i>>1]==0) vis[i>>1]=1,edge++;
		dfs(V[i],(col+W[i])%3);
	}
	return;
}