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>

const int maxn = 1e5 + 10;
typedef long long ll;
int n, m, i, j, k;
ll ans, hd[maxn], nxt[maxn << 1], ver[maxn << 1], wei[maxn << 1], cnte;
ll col[maxn], a[maxn]; bool succ;
inline void adde(int u, int v, int w) {
	ver[++cnte] = v, wei[cnte] = w, nxt[cnte] = hd[u], hd[u] = cnte;
}
void dfs(int u) {
	a[col[u]]++;
	for (int i = hd[u]; i; i = nxt[i]) {
		int v = ver[i], w = wei[i];
		if (w == 1) a[3]++;
		if (col[v] == -1) {
			col[v] = (col[u] + w) % 3;
			dfs(v); 
		} else if (col[v] != (col[u] + w) % 3) {
			succ = 1;
		}
	}
}

int main() {
//	freopen("chain.in", "r", stdin);
//	freopen("chain.out", "w", stdout);  
	scanf("%d %d", &n, &m);
	for (int i = 1, u, v; i <= m; i++) {
		scanf("%d %d", &u, &v);
		adde(u, v, 1), adde(v, u, 2); 
	}
	memset(col, -1, sizeof(col));
	for (int i = 1; i <= n; i++) {
		if (col[i] == -1) {
			a[col[i] = 0] = a[1] = a[2] = a[3] = succ = 0;
			dfs(i);
			if (succ) {
				ll tmp = a[0] + a[1] + a[2];
			  ans += 1ll * tmp * tmp;
			  continue;
		  }   
		  if ((!a[0]) || (!a[1]) || (!a[2])) {
			  ans += a[3];
			  continue;
		  }
		  ans += 1ll * a[0] * a[1];
		  ans += 1ll * a[1] * a[2];
		  ans += 1ll * a[0] * a[2];
		}
	}
	printf("%lld\n", ans);
	return 0;  
}