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>
using namespace std;
using PII = pair<int, int>;
using ll = long long;
#define ff first 
#define ss second 
const int N = 100000 + 10;
vector<PII> v[N];
vector<int> S;
int n, m, a, b, col[N], C[4], ban, tot;
int fit(int x) {
    while (x > 3) x -= 3;
    while (x < 1) x += 3;
    return x;
}
void dfs(int x, int c) {
    if (col[x]) {
        if (col[x] != c) ban = 1;
        return;
    }
    S.push_back(x);
    col[x] = c;
    for (auto E : v[x]) {
        tot++;
        dfs(E.ff, fit(c + E.ss));
    }
}
int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d", &a, &b);
        v[a].push_back({b, 1});
        v[b].push_back({a, -1});
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (col[i]) continue;
        memset(C, 0, sizeof(C));
        S.clear();
        ban = tot = 0;
        dfs(i, 1);
        for (auto x : S) C[col[x]]++;
        if (ban)
            ans += 1ll * S.size() * S.size();
        else if (C[1] == 0 || C[2] == 0 || C[3] == 0)
            ans += tot / 2;
        else
            ans += 1ll * C[3] * C[1] + 1ll * C[1] * C[2] + 1ll * C[2] * C[3];
    }
    printf("%lld\n", ans);
    return 0;
}