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 <algorithm>
#include <cstring>
#include <cctype>
#include <cstdio>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e5+5;
struct Edge
{
    int next, to, w;
    Edge(int next = 0, int to = 0, int w = 0):next(next), to(to), w(w) {};
}edge[N<<1];
int tot, head[N];
void add(int x, int y, int z) { edge[++tot] = Edge(head[x], y, z); head[x] = tot; }
int n, m, c[N];
int64 ans, f[3], s;
bool color(int x, int col)
{   
    if(c[x]) return c[x] == col+1;   
    c[x] = col+1, ++f[col];
    bool ret = true;
    for(int i = head[x]; i; i = edge[i].next)
    {
        int y = edge[i].to, z = edge[i].w; s += z == 1;
        if(!color(y, col+z >= 3?col+z-3:col+z)) ret = false;
    }
    return ret;
}
int main()
{
    n = read(), m = read();
    for(int i = 1; i <= m; ++i)
    {
        int x = read(), y = read();
        add(x, y, 1), add(y, x, 2);
    }
    for(int x = 1; x <= n; ++x)
        if(!c[x])
        {
            s = f[0] = f[1] = f[2] = 0;
            if(!color(x, 1)) s = f[0]+f[1]+f[2], ans += s*s;
            else if(f[0]&&f[1]&&f[2]) ans += f[0]*f[1]+f[1]*f[2]+f[0]*f[2];
            else ans += s;
        }
    printf("%lld\n", ans);
    return 0;
}