DSU BY 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],sz[N],mx[N],ans;
//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;
    if(sz[x] > sz[y])
        swap(x,y);
    ans -= min(mx[x],mx[y]);
    //cout << ans << " ";
    mx[y] = max(mx[x],mx[y]);
    parent[x] = y;
    sz[y] += sz[x];



}
int main()
{
    fast;
    ll n , q;
    cin >> n >> q ;
    for(int i = 1 ;  i <= n ; i++ ){
        parent[i] =  i;
        sz[i] = i ;
        mx[i] =  i;
    }

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

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



    }























    return 0;

}