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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

const int MAXN = 100000 + 1000;


int n, m;
vector<int> edg[MAXN], redg[MAXN];
int col[MAXN];
int num[3], ne, nv;

bool dfs(int x, int c)
{
	if(col[x] != -1)
		return col[x] == c;
	col[x] = c;
	num[col[x]]++, ne += edg[x].size(), nv += 1;
	bool ret = true;
	for(int i = 0; i < edg[x].size(); i++)
		if(!dfs(edg[x][i], (c + 1) % 3))
			ret = false;
	for(int i = 0; i < redg[x].size(); i++)
		if(!dfs(redg[x][i], (c + 2) % 3))
			ret = false;
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);

	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		edg[x].push_back(y);
		redg[y].push_back(x);
	}

	memset(col, -1, sizeof(col));

	long long ans = 0;
	for(int i = 1; i <= n; i++)
		if(col[i] == -1)
		{
			memset(num, 0, sizeof(num));
			nv = ne = 0;
			bool flag = dfs(i, 0);
			if(flag)
			{
				if(num[0] && num[1] && num[2])
					ans += (long long)num[0] * num[1] + (long long)num[1] * num[2] + (long long)num[2] * num[0];
				else
					ans += ne;
			}
			else
			{
				ans += (long long)nv * nv;
			}
		}
	cout << ans << endl;

	return 0;
}