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 <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
#define MAXN 100000
#define ll long long
#define rint register int
#define gc() getchar()
inline int read(int r=0,int s=0,int c=gc()){for(;c<48||c>57;s=c,c=gc());for(;c>=48&&c<=57;(r*=10)+=c-48,c=gc());return s^'-'?r:-r;}
vector<int> e[MAXN+5], f[MAXN+5]; bool sl; int color[MAXN+5], n, m; ll Ans, c[3], s;
void DFS(int p, int x){if(~color[p]){sl |= color[p]^x; return;} color[p] = x, ++c[x], ++s, m += e[p].size(); for(auto v:e[p]) DFS(v,-~x%3); for(auto v:f[p]) DFS(v,-~-~x%3);}
int main()
{
	n = read(); for(rint a, b = c[0] = read(); c[0]; a = read(), b = read(), e[a].push_back(b), f[b].push_back(a), c[0]--); memset(color+1,-1,n<<2);
	for(rint i = 1; i <= n; color[i]<0 ? DFS(i,s=c[0]=c[1]=c[2]=m=sl=0), Ans = sl?Ans+s*s:c[0]&&c[1]&&c[2]?Ans+c[0]*c[1]+c[1]*c[2]+c[2]*c[0]:Ans+m : 0, i++); printf("%lld\n",Ans); return 0;
}