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;
#define int long long
#define pii pair <int , int>
#define F first
#define S second
const int N = 1e5 + 10;
int cnt[3], cntm, c[N];
vector <pii> g[N];

bool dfs(int v, int col = 0)
{
    bool flag = 0;
    c[v] = col;
    cnt[col]++;
    cntm += g[v].size();
    for (auto u : g[v]) {
        if (c[u.F] == -1) flag |= dfs(u.F, (col + u.S) % 3);
        else if (c[u.F] != (col + u.S) % 3) flag = 1;
    }
    return flag;
}

int32_t main()
{
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        g[x].push_back({y, 1});
        g[y].push_back({x, 2});
    }
    int ans = 0;
    fill(c, c + N, -1);
    for (int i = 1; i <= n; i++) if (c[i] == -1) {
        cnt[0] = cnt[1] = cnt[2] = cntm = 0;
        if (dfs(i)) ans += (cnt[0] + cnt[1] + cnt[2]) * (cnt[0] + cnt[1] + cnt[2]);
        else {
            if (cnt[0] && cnt[1] && cnt[2]) ans += cnt[0] * cnt[1] + cnt[1] * cnt[2] +  cnt[2] * cnt[0];
            else ans += cntm/2;
        }
    }
    cout << ans << "\n";
}