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<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
const int N=2e5+100;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int head[N],nxt[N],to[N],w[N];
int c[3],col[N],e;
bool vis[N],flag;
inline void dfs(int k,int d) {
	c[col[k]=d]++;vis[k]=true;
	for (int i=head[k];i;i=nxt[i],e++)
		if (!vis[to[i]]) dfs(to[i],(d+w[i])%3);
		else if ((d+w[i])%3!=col[to[i]]) flag=false;
}
int main()
{
	int n=gi(),m=gi(),i,a,b,tot=0;LL ans=0;
	for (i=1;i<=m;i++) {
		a=gi(),b=gi();
		to[++tot]=b,nxt[tot]=head[a],head[a]=tot,w[tot]=1;
		to[++tot]=a,nxt[tot]=head[b],head[b]=tot,w[tot]=2;
	}
	for (i=1;i<=n;i++)
		if (!vis[i]) {
			c[0]=c[1]=c[2]=e=0;
			flag=true;
			dfs(i,0);
			if (flag)
				if (c[0]&&c[1]&&c[2])
					ans+=1LL*c[0]*c[1]+1LL*c[0]*c[2]+1LL*c[1]*c[2];
				else ans+=e>>1;
			else ans+=1LL*(c[0]+c[1]+c[2])*(c[0]+c[1]+c[2]);
		}
	printf("%lld\n",ans);
	return 0;
}