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 <vector>
#include <queue>
using namespace std;

int main()
{
  int n,m;
  scanf("%d%d",&n,&m);
  vector<vector<int> > e(n),r(n);
  for(int i=0;i<m;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    a--;
    b--;
    e[a].push_back(b);
    r[b].push_back(a);
  }
  long long ans=0;
  static int V[100000];
  for(int i=0;i<n;i++){
    V[i]=-1;
  }
  for(int i=0;i<n;i++){
    if(V[i]!=-1){
      continue;
    }
    queue<int> Q;
    Q.push(i);
    bool F=0;
    int c=0,C[3]={0};
    V[i]=0;
    C[0]++;
    while(!Q.empty()){
      int j=Q.front();
      Q.pop();
      int v=V[j];
      for(int x=0;x<e[j].size();x++){
	int k=e[j][x];
	c++;
	if(V[k]==-1){
	  V[k]=(v+1)%3;
	  C[V[k]]++;
	  Q.push(k);
	}
	else if(V[k]!=(v+1)%3){
	  F=1;
	}
      }
      for(int x=0;x<r[j].size();x++){
	int k=r[j][x];
	if(V[k]==-1){
	  V[k]=(v+2)%3;
	  C[V[k]]++;
	  Q.push(k);
	}
	else if(V[k]!=(v+2)%3){
	  F=1;
	}
      }
    }
    if(F){
      int A=C[0]+C[1]+C[2];
      ans+=(long long)A*A;
    }
    else if(C[1]==0||C[2]==0){
      ans+=c;
    }
    else{
      ans+=(long long)C[0]*C[1]+(long long)C[1]*C[2]+(long long)C[2]*C[0];
    }
  }
  printf("%lld\n",ans);
  return 0;
}