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 <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Edge {
  int t,v,next;
  Edge() {}
  Edge(int a,int b,int c):t(a),v(b),next(c) {}
};

Edge e[200005];
int head[100005];

int num[100005],use[3],s1,s2;
bool ok,vis[100005];

void dfs(int x) {
  use[num[x]]++;
  vis[x]=1;s2++;
  for(int i=head[x];i;i=e[i].next) {
  	int u=e[i].t;
  	s1++;
  	if (!vis[u]) {
  		num[u]=((num[x]+e[i].v)%3);
  		dfs(u);
	  }
	else if (num[u]!=((num[x]+e[i].v)%3)) ok=0;
  }
}

int main() {
  int n,m;
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++) {
  	int x,y;
  	scanf("%d%d",&x,&y);
  	e[2*i-1]=Edge(y,1,head[x]);
  	head[x]=2*i-1;
  	e[2*i]=Edge(x,2,head[y]);
  	head[y]=2*i;
  }
  ll ans=0;
  for(int i=1;i<=n;i++)
    if (!vis[i]) {
    	memset(use,0,sizeof(use));
    	ok=1;s1=s2=0;
    	dfs(i);
    	if (!ok) ans+=(ll)s2*s2;
    	else {
    		for(int j=0;j<3;j++)
    		  if (!use[j]) ok=0;
    		if (!ok) ans+=(s1>>1);
    		else ans+=(ll)use[0]*use[2]+(ll)use[1]*use[2]+(ll)use[0]*use[1];
		}
	}
  printf("%lld\n",ans);
  return 0;
}