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<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<queue>
#define LL long long
using namespace std;
inline int read( )
{
  int sum=0;char c=getchar( );bool f=0;
  while(c<'0'||c>'9') {if(c=='-') f=1;c=getchar( );}
  while(c>='0'&&c<='9') {sum=sum*10+c-'0';c=getchar( );}
  if(f) return -sum;
  return sum;
}
const int N=100005;
int n,m;
struct ex{int num,next,w;}map[N*2];
int head[N],col[N],len;
inline void link(int x,int y)
{
  len++;map[len]=(ex){y,head[x],1};head[x]=len;
  len++;map[len]=(ex){x,head[y],2};head[y]=len;
}
bool vis[N],NO;int num[3],tot,bot;
inline void dfs(int k)
{
  vis[k]=1;num[col[k]]++;tot++;
  int i,x,u=col[k],y;
  for(i=head[k];i;i=map[i].next)
    {
      x=map[i].num;bot++;
      y=(u+map[i].w)%3;
      if(vis[x]) NO|=(col[x]!=y);
      else col[x]=y,dfs(x);
    }
}
int main( )
{
  int i,x,y;LL ans=0;
  n=read( );m=read( );
  for(i=1;i<=m;i++) x=read( ),y=read( ),link(x,y);
  for(i=1;i<=n;i++)
    {
      if(vis[i]) continue;
      num[0]=num[1]=num[2]=0;
      NO=0;tot=0;bot=0;dfs(i);
      if(NO) ans+=1LL*tot*tot;
      else if(num[0]&&num[1]&&num[2]) ans+=1LL*num[0]*num[1]+1LL*num[1]*num[2]+1LL*num[2]*num[0];
      else ans+=bot>>1;
    }
  printf("%lld",ans);
  return 0;
}