Input:
4 3
1 2
2 3
3 1

Output:
2
1
1

Comment:
(1, 3, 4), (2, 3, 4)
(1, 3, 4)
(1, 2, 3)

Input:
3 5
1 2
2 3
3 1
1 2
1 2

Output:
0
0
1
0
1

Comment:
There are no valid triangle (2, 3), (3, 1) are green while (1, 2) is red
There are no valid triangle (3, 1) is green while (1, 2), (2, 3) are red
(1, 2, 3)
There are no valid triangle (2, 3), (3, 1) are green while (1, 2) is red
(1, 2, 3)

Input:
2 5
1 2
1 2
1 2
1 2
1 2

Output:
0
0
0
0
0

Comment:
There are only two nodes

#include <iostream>
#include <vector>
#include <set>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<vb> vmb;
typedef vector<vi> vmi;
typedef set<int> si;
typedef set<pi> spi;
typedef vector<si> vsi;

int main()
{
    int n, q;
    cin >> n >> q;

    vsi f(n + 1);
    ll pre = 1LL * n * (n - 1) * (n - 2) / 6;
    while (q--)
    {
        int u, v;
        cin >> u >> v;

        ll cnt = pre;
        for (int w = 1; w <= n; ++w)
        {
            if (w == u || w == v) continue;
            
            int t = f[u].count(v) + f[v].count(w) + f[w].count(u);
            cnt -= (t == 0 || t == 3);
        }

        if (f[u].count(v)) f[u].erase(v); else f[u].insert(v);
        if (f[v].count(u)) f[v].erase(u); else f[v].insert(u);

        for (int w = 1; w <= n; ++w)
        {
            if (w == u || w == v) continue;
            
            int t = f[u].count(v) + f[v].count(w) + f[w].count(u);
            cnt += (t == 0 || t == 3);
        }
        pre = cnt;
        std::cout << cnt << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <map>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(u) (u).begin(), (u).end()
#define FastIO ios::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<vb> vmb;
typedef vector<vi> vmi;

int readInt() { int u; return cin >> u, u; }
ll readLong() { ll u;  return cin >> u, u; }

int main()
{
    FastIO;

    int n = readInt();
    ll total = 1LL * n * (n - 1) * (n - 2) / 6;

    vi G(n, n - 1);
    vi R(n, 0); 
    
    ll res = 0;
    map<pl, bool> M;
    for (int q = readInt(); q--;)
    {
        ll u = readLong() - 1;
        ll v = readLong() - 1;

        if (u > v) swap(u, v);

        int delta = (M[{u, v}] ^= 1) ? +1 : -1;

        res -= (R[u] * G[u] + R[v] * G[v]);
        R[u] += delta; R[v] += delta;
        G[u] -= delta; G[v] -= delta;
        res += (R[u] * G[u] + R[v] * G[v]);

        cout << (total - res / 2) << endl;
    }

    return 0;
}