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:
//Ilm kave oi, you know ...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 3;
const int infint = (int)1e9 + 3;
const ll inf = (ll)1e12;
int n, m, sz, cyc, visited[MAXN], md0, md1, md2, e;
vector<pair<int, int> > H[MAXN];
void dfs(int u, int num)
{
	sz++;
	visited[u] = num;
	if(num == 0)	
		md0++;
	else
	if(num == 1)
		md1++;
	else
		md2++;
	
	for (auto v : H[u])
	{
		e++;
		int nw = num;
		if(v.second == 0)
			nw = (nw + 1) % 3;
		else
			nw = (nw + 2) % 3;
		if(visited[v.first] == -1)
			dfs(v.first, nw);
		else
		if(visited[v.first] != nw)
			cyc = 1;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		H[u].push_back({v, 0});
		H[v].push_back({u, 1});
	}
	memset(visited, -1, sizeof visited);
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		if(visited[i] == -1)
		{
			sz = 0, cyc = 0, md0 = 0, md1 = 0, md2 = 0, e = 0, dfs(i, 0);
			if(cyc == 1)
				ans += 1LL * sz * sz;
			else
			if(md0 && md1 && md2)
				ans += 1LL * md0 * md1 + 1LL * md1 * md2 + 1LL * md2 * md0;
			else
				ans += e / 2;
		}
	cout << ans;
}