DSU WITHOUT UNION BY SIZE OR RANK

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e5 + 1;
const int mod = 1e9 + 7;

ll parent[N];
//dsu
//path compression without union by size or rank;
/*ll find(ll v)
{
    if(v == parent[v])
        return v;
    return parent[v] = find(parent[v]);
}*/
//non - recursive implementation of path compression find function
ll find(ll v)
{
    while(v != parent[v])
    {
        parent[v] = parent[parent[v]];
        v = parent[v];
    }
    return v;
}
void union_set(ll x , ll y)
{
    x = find(x);
    y = find(y);
    if(x == y)
        return;
    parent[min(x,y)] = max(x,y);
}
int main()
{
    fast;
    ll n , q;
    cin >> n >> q ;
    for(int i = 1 ;  i <= n ; i++ )
        parent[i] =  i;

    ll ans = n*(n+1)/2;
    while(q--)
    {
        ll x , y;
        cin >> x >> y ;

        if(find(x) == find(y)){
        cout << ans << "\n";
        continue;
        }
        ans -= min(find(x) , find(y));
        union_set(x,y);
        cout << ans << "\n";



    }























    return 0;

}