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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+500;
struct Edge{int v,w;}e[N];
int fst[N],nxt[N],cnt[5],vis[N],col[N],siz,en,fail,n,m,mm=1,evis[N];
long long ans;
void ade(int u,int v,int w){e[++mm]=(Edge){v,w},nxt[mm]=fst[u],fst[u]=mm;}
void dfs(int u,int c)
{
    vis[u]=1;col[u]=c;++cnt[c];++siz;
    for(int i=fst[u];i;i=nxt[i])
    {
        int v=e[i].v;if(!evis[i])evis[i]=evis[i^1]=1,++en;
		int t=c+e[i].w;if(t==4)t=1;if(t==0)t=3;
        if(vis[v])
        {
            if(col[v]!=t)fail=1;
            continue;
        }
        dfs(v,t);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),ade(u,v,1),ade(v,u,-1);
    for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            siz=en=cnt[1]=cnt[2]=cnt[3]=fail=0;
            dfs(i,1);
            if(fail)ans+=1ll*siz*siz;
            else if(cnt[1]&&cnt[2]&&cnt[3])ans+=1ll*cnt[1]*cnt[2]+1ll*cnt[2]*cnt[3]+1ll*cnt[3]*cnt[1];
            else ans+=en;
        }
    cout<<ans<<endl;
}