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 <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll;
#define rep(i, a, b) for (int i = a; i <= b; ++ i)
const int maxn = 100010;
using namespace std;
bool vis[maxn]; int col[maxn]; ll h[3], ans;
int n, m, e, ter[maxn << 1], nxt[maxn << 1], lnk[maxn], opt[maxn];
void add(int x, int y) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e;
	ter[++ e] = x, nxt[e] = lnk[y], lnk[y] = e;
}
void bfs(int st) {
	int he = 0, ta = 1, ed = 0; opt[1] = st, vis[st] = false;
	col[st] = 0; bool flg = true;
	while (he != ta) {
		++ he; int u = opt[he];
		for (int i = lnk[u]; i; i = nxt[i]) {
			if (i & 1) ++ ed;
			if (vis[ter[i]]) {
				vis[ter[i]] = false;
				if (i & 1) col[ter[i]] = (col[u] + 1) % 3;
					else col[ter[i]] = (col[u] + 2) % 3;
				opt[++ ta] = ter[i];
			} else {
				if (i & 1) flg &= (col[ter[i]] == (col[u] + 1) % 3);
					else flg &= (col[ter[i]] == (col[u] + 2) % 3);
			}
		}
	}
	if (flg) {
		h[0] = h[1] = h[2] = 0;
		rep(i, 1, ta) ++ h[col[opt[i]]];
		if (!h[0] || !h[1] || !h[2]) { ans += ed; return ; }
		ans += h[0] * h[1] + h[1] * h[2] + h[2] * h[0];
	} else ans += (ll) ta * ta;
}
int main() {
	scanf("%d%d", &n, &m); int x, y;
	rep(i, 1, m) scanf("%d%d", &x, &y), add(x, y);
	memset(vis, true, sizeof(vis));
	ans = 0;
	rep(i, 1, n) if (vis[i]) bfs(i);
	printf("%lld\n", ans);
	return 0;
}