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 <algorithm>
#include <cstdio>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
struct E {int v, w, nt;} e[N<<1];
int n, m, ok, poi, edg, tot = 1, h[N], pai[N], cnt[3], vis[N<<1]; LL ans;

inline void add(int u, int v, int w1, int w2) {
	e[++tot] = (E){v, w1, h[u]}, h[u] = tot;
	e[++tot] = (E){u, w2, h[v]}, h[v] = tot;
}

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

inline void dfs(int x, int c) {
	if (~pai[x]) {
		if (pai[x] != c) ok = 0;
		return;
	}
	++cnt[pai[x] = c], ++poi;
	for (int i = h[x]; i; i = e[i].nt)
		if (!vis[i] && !vis[i ^ 1]) {
			vis[i] = vis[i ^ 1] = 1, ++edg;
			dfs(e[i].v, (c + e[i].w) % 3);
		}
}

int main() {
	int u, v; in(n), in(m), fill(pai, pai + N, -1);
	for (int i = 1; i <= m; ++i) in(u), in(v), add(u, v, 1, 2);
	for (int i = 1; i <= n; ++i) {
		if (~pai[i]) continue;
		poi = edg = 0, ok = 1;
		fill(cnt, cnt+3, 0), dfs(i, 0);
		if (!ok) ans += 1LL * poi * poi;
		else if (!cnt[0] || !cnt[1] || !cnt[2]) ans += (LL)edg;
		else ans += 1LL * cnt[0] * cnt[1] + 1LL * cnt[1] * cnt[2] + 1LL * cnt[2] * cnt[0];
	}
	printf("%lld\n", ans);
	return 0;
}