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 For(i, j, k) for(int i = j; i <= k; i++)
#define pb push_back

using namespace std;

const int N = 100010;

int fa[N];

int find(int x){
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int n, m;
vector<int> G[N], rev[N], blk[N];

int dep[N];
bool vis[N];

void DFS(int o){
	vis[o] = true;
	for(int v : G[o]){
		if(vis[v]) continue;
		dep[v] = dep[o] + 1;
		DFS(v);
	}
	for(int v : rev[o]){
		if(vis[v]) continue;
		dep[v] = dep[o] - 1;
		DFS(v);
	}
}

int main(){
	scanf("%d%d", &n, &m);
	For(i, 1, n) fa[i] = i;
	For(i, 1, m){
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v), rev[v].pb(u);
		fa[find(u)] = find(v);
	}
	For(i, 1, n) blk[find(i)].pb(i);

	long long ans = 0;
	For(i, 1, n) if(fa[i] == i){
		
		vis[i] = true, dep[i] = 0;
		DFS(i);
		bool checked = false;
		int sz = blk[i].size(), cnt = 0;

		for(int o : blk[i]){
			for(int v : G[o]){
				if(((dep[v] - dep[o]) % 3 + 3) % 3 != 1){
					checked = true;
					break;
				}
				++cnt;
			}
			if(checked) break;
		}

		if(checked){
			ans += 1ll * sz * sz;
			continue;
		}
		
		int tot[3] = {0};
		for(int o : blk[i]) tot[(dep[o] % 3 + 3) % 3]++;
		if(!tot[0] || !tot[1] || !tot[2]){
			ans += cnt;
			continue;
		}

		For(j, 0, 2) ans += 1ll * tot[j] * tot[(j + 1) % 3];
	}
	printf("%lld\n", ans);
	return 0;
}