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;
const int N = 100005;
int n, m, d, stat, M[N], C[4];
vector < int > Adj[N], Adt[N];
void DFS(int v)
{
    C[M[v]] ++;
    d += (int)Adj[v].size();
    for (int &u : Adj[v])
    {
        if (!M[u])
            M[u] = M[v] % 3 + 1, DFS(u);
        if (M[u] != M[v] % 3 + 1)
            stat = 1;
    }
    for (int &u : Adt[v])
    {
        if (!M[u])
            M[u] = (M[v] + 1) % 3 + 1, DFS(u);
        if (M[u] != (M[v] + 1) % 3 + 1)
            stat = 1;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int v, u;
        scanf("%d%d", &v, &u);
        Adj[v].push_back(u);
        Adt[u].push_back(v);
    }
    long long tot = 0;
    for (int i = 1; i <= n; i++)
        if (!M[i])
        {
            C[1] = C[2] = C[3] = d = 0;
            stat = 2; M[i] = 1; DFS(i);
            if (stat == 1) tot += 1LL * (C[1] + C[2] + C[3]) * (C[1] + C[2] + C[3]);
            else if (!C[1] || !C[2] || !C[3]) tot += d;
            else if (stat == 2) tot += 1LL * C[1] * C[2] + 1LL * C[2] * C[3] + 1LL * C[3] * C[1];
        }
    return !printf("%lld\n", tot);
}