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 rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int maxn = 200200;
typedef long long ll;
const int mod = 998244353;
inline ll pow(ll a,int b,int ans = 1) {
	for(;b;b >>= 1,a = a * a % mod) if(b & 1)
		ans = ans * a % mod;
	return ans;
}
inline ll inverse(int x){ return pow(x, mod - 2); }
struct T{ int to, nxt, v; } way[maxn << 1];
int h[maxn], num;
inline void link(int x,int y) {
	way[++num] = {y,h[x],1}, h[x] = num;
	way[++num] = {x,h[y],2}, h[y] = num;
}
int n, m;
int vis[maxn], c[maxn], ct[3], flag = 0, edge = 0;
inline void dfs0(int x) {
	vis[x] = 1; ++ ct[c[x]];
	for(int i = h[x];i;i = way[i].nxt) {
		++ edge;
		int to = way[i].to;
		int v = (c[x] + way[i].v) % 3;
		if(c[to] != -1 && c[to] != v) flag = 1;
		c[to] = v;
		if(!vis[to]) dfs0(to);
	}
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 0, x, y;i < m;++i) {
		cin >> x >> y, link(x, y);
	}
	rep(i, 1, n) c[i] = -1;
	ll ans = 0;
	rep(i, 1, n) if(!vis[i]) {
		c[i] = 0, dfs0(i);
		if(flag) {
			ans += ll(ct[0] + ct[1] + ct[2]) * (ct[0] + ct[1] + ct[2]);
		} else if(!ct[2] || !ct[1]) {
			ans += edge / 2;
		} else {
			ans += (ll) ct[0] * ct[1] + (ll) ct[1] * ct[2] + (ll) ct[2] * ct[0];
		}
		edge = flag = ct[0] = ct[1] = ct[2] = 0;
	}
	cout << ans << '\n';
}