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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;

LL n,m,ans = 0,col[3],cnt,rep,ect;
LL vis[200005] = {0},cco[200005] = {0};

LL ec = 0,nxt[400005],to[400005],hed[200005] = {0},w[400005];
void add_edge(LL f,LL t,LL cst){
	++ ec; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec; w[ec] = cst;
}

void dfs(LL u,LL co){
	cnt ++; col[co] ++;
	vis[u] = 1; cco[u] = co;
	for(LL i = hed[u];i;i = nxt[i]){
		LL v = to[i];
		if(w[i] == 1) ect ++;
		if(vis[v]){
			if((co + w[i] + 3) % 3 != cco[v]) rep = 1;
			continue;
		}
		dfs(v,(co + w[i] + 3) % 3);
	}
}

int main(){
	LL u,v;
	cin >> n >> m;
	for(LL i = 1;i <= m;i ++){
		cin >> u >> v;
		add_edge(u,v,1);
		add_edge(v,u,-1);
	}
	memset(vis,0,sizeof(vis));
	for(LL i = 1;i <= n;i ++){
		if(vis[i]) continue;
		col[0] = col[1] = col[2] = 0;
		cnt = 0; rep = 0; ect = 0; dfs(i,0);
//		cout << i << ' ' << col[0] << ' ' << col[1] << ' ' << col[2] << endl;
		if(rep) ans += cnt * cnt;
		else if(col[0] && col[1] && col[2]) ans += (col[0] * col[1] + col[1] * col[2] + col[2] * col[0]);
		else ans += ect;
	}
	cout << ans << endl;
	return 0;
}