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>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const int N=100005;
int c[N],s[4],n,m,a,b,flag,E;
vi e[N],r[N];
ll ans;

void dfs(int u,int col){
	if(c[u]){
		flag|=(c[u]!=col);
		return;
	}
	s[c[u]=col]++;
	for(auto v:e[u]) dfs(v,col%3+1),E++;
	for(auto v:r[u]) dfs(v,(col+1)%3+1),E++;
}

int main(){
	read(n),read(m);
	rep(i,1,m){
		read(a),read(b);
		e[a].pb(b),r[b].pb(a);
	}
	rep(i,1,n){
		if(c[i]) continue;
		s[1]=s[2]=s[3]=E=flag=0;
		dfs(i,1);
		if(flag){
			ll t=s[1]+s[2]+s[3];
			ans+=t*t;
		}
		else if(s[1]&&s[2]&&s[3]){
			ans+=(ll)s[1]*s[2]+(ll)s[2]*s[3]+(ll)s[3]*s[1];
		}
		else ans+=E/2;
	}
	cout<<ans<<endl;
	return 0;
}