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 LL long long
using namespace std;
const int N = 2e5 + 10;

int n, m, E, cnt;
int fir[N], nex[N], arr[N], val[N], vis[N];
LL A, B, C, flag, col[N];

inline void Add_Edge(int x, int y, int w) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y; val[E] = w;
}

void dfs(int x) {
	vis[x] = 1;
	if (col[x] == 0) ++A;
	if (col[x] == 1) ++B;
	if (col[x] == 2) ++C;
	for (int i = fir[x]; i; i = nex[i]) {
		if (val[i] == 1) ++cnt;
		if (vis[arr[i]]) {
			if (col[arr[i]] != (col[x] + val[i]) % 3)
				flag = 1;
		}
		else {
			col[arr[i]] = (col[x] + val[i]) % 3;
			dfs(arr[i]);
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		Add_Edge(x, y, 1);
		Add_Edge(y, x, 2);
	}
	memset(col, 0xff, sizeof col);
	LL ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue;
		A = B = C = cnt = flag = 0;
		col[i] = 0;
		dfs(i);
		if (flag) ans += (A + B + C) * (A + B + C);
		else if (!A || !B || !C) ans += cnt;
		else ans += (A * B) + (B * C) + (A * C);
	}
	cout << ans << endl;
	return 0;
}