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:
/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+10;
struct node{int to,nxt,w;}e[maxn<<1];
int n,m,tot,bel,sec,flag,cnt[3],head[maxn],vis[maxn],col[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(ll x){print(x);puts("");}
void add(int u,int v,int w){e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;}
void dfs(int x){
    cnt[col[x]]++;vis[x]=1;bel++;
    for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to){
        if(e[i].w==1)sec++;
        if(!vis[v])col[v]=(col[x]+e[i].w+3)%3,dfs(v);
        else if(col[v]!=(col[x]+e[i].w+3)%3)flag=1;
    }
}
int main(){
    n=read();m=read();ll ans=0;
    for(int i=1;i<=m;i++){int u=read(),v=read();add(u,v,1);add(v,u,-1);}
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        memset(cnt,0,sizeof(cnt));
        bel=sec=flag=0;dfs(i);
        if(flag)ans+=1ll*bel*bel;
        else if(cnt[0]&&cnt[1]&&cnt[2])ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[1]*cnt[2]+1ll*cnt[2]*cnt[0];
        else ans+=sec;
    }write(ans);
    return 0;
}