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<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e6+5;
struct edge{int to,len,nxt;}e[N<<1];
int h[N],tot=1,n,m,col[N],sum[4],f1=0,f2=0,sz=0,ss;
ll ans=0;
void adde(int x,int y,int z){e[tot]=(edge){y,z,h[x]};h[x]=tot++;}
void dfs(int u){
    sz++,sum[col[u]]++;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to;if(e[i].len==1)ss++;
        if(!col[v])col[v]=(col[u]+e[i].len-1)%3+1,dfs(v);
        else if(col[v]!=(col[u]+e[i].len-1)%3+1)f2=1;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y),adde(x,y,1),adde(y,x,2);}
    for(int i=1;i<=n;i++){
        if(col[i])continue;
        col[i]=1,f1=f2=sz=sum[1]=sum[2]=sum[3]=ss=0;dfs(i);
        //cout<<f1<<" "<<f2<<endl;
        if(f2)ans+=1ll*sz*sz;
        else if(sum[1]&&sum[2]&&sum[3])ans+=sum[1]*1ll*sum[2]+sum[2]*1ll*sum[3]+sum[3]*1ll*sum[1];
        else ans+=ss;
    }
    printf("%lld\n",ans);
}