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 <stdint.h>

std::vector<int64_t> fwd[100000];
std::vector<int64_t> rev[100000];

int64_t vis[100000];

int64_t cnt[4];
bool one;
int64_t edges=0;

void dfs(int64_t node,int64_t color){
  if(vis[node]==color) return;
  if(vis[node]!=0){one=true;return;}
  vis[node]=color;
  cnt[color%3]++;
  for(int64_t nxt:fwd[node]){
    dfs(nxt,color%3+1);
    edges++;
  }
  for(int64_t prv:rev[node]){
    dfs(prv,(color+1)%3+1);
    edges++;
  }
}

int main(){
  int64_t N,M;
  scanf("%ld %ld",&N,&M);
  for(int64_t i=0;i<M;i++){
    int64_t A,B;
    scanf("%ld %ld",&A,&B);
    A--,B--;
    fwd[A].push_back(B);
    rev[B].push_back(A);
  }
  int64_t total=0;
  for(int64_t i=0;i<N;i++){
    if(vis[i]) continue;
    std::fill(cnt,cnt+3,0);
    one=false;
    edges=0;
    dfs(i,1);
    if(one){
      int64_t here=cnt[0]+cnt[1]+cnt[2];
      total+=here*here;
    }else if(cnt[0]&&cnt[1]&&cnt[2]){
      for(int64_t i=0;i<3;i++){
	total+=cnt[i]*cnt[(i+1)%3];
      }
    }else{
      total+=edges/2;
    }
  }
  /*
  for(int64_t i=0;i<N;i++){
    printf("color[%ld]=%ld\n",i,vis[i]);
  }
  */
  printf("%ld\n",total);
  return 0;
}