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:
// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> v[2][maxn];
bool mark[maxn];
int numb[maxn];

bool IS = 0;
int cnt[3], M;

void dfs(int u){
    M+= sz(v[0][u]);
    cnt[ numb[u] ]++;
    mark[u] = 1;
    for(int y : v[0][u]){
	if(mark[y])
	    IS|= numb[y] != (numb[u] + 1) % 3;
	else
	    numb[y] = (numb[u] + 1) %3, dfs(y);
    }
    for(int y : v[1][u]){
	if(mark[y])
	    IS|= numb[y] != (numb[u] + 2) % 3;
	else
	    numb[y] = (numb[u] + 2) %3, dfs(y);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    ll ans = 0;
    
    int n, m;
    cin >> n >> m;
    while(m--){
	int a, b;
	cin >> a >> b;
	v[0][a].PB(b);
	v[1][b].PB(a);
    }
    for(int i = 1; i <= n; i++){
	if(mark[i] == 0){
	    IS = 0, cnt[0] = cnt[1] = cnt[2] = M = 0;
	    dfs(i);
	    if(IS)
		ans+= 1ll * (cnt[0] + cnt[1] + cnt[2]) * (cnt[0] + cnt[1] + cnt[2]);
	    else if(min({cnt[0], cnt[1], cnt[2]}) > 0)
		ans+= 1ll * cnt[0] * cnt[1] + 1ll * cnt[1] * cnt[2] + 1ll * cnt[2] * cnt[0];
	    else
		ans+= M;
	}
    }
    return cout << ans << endl, 0;
}