CSES – Road Construction

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 1e5+5;
int n,m;
//
struct DSU{
    int n, boss[maxn], sz[maxn];
    int components, maxsz;
    DSU(int _n): n(_n), components(_n), maxsz(1) {
        for(int i=1;i<=_n;i++){
            boss[i] = i;
            sz[i] = 1;
        }
    }
    int find(int a){
        return (a == boss[a] ? a : boss[a] = find(boss[a]));
    }
    void join(int a,int b){
        a = find(a), b = find(b);
        if(a == b) return;
        boss[a] = b;
        sz[b] += sz[a];
        maxsz = max(maxsz, sz[b]);
        components--;
    }
};
signed main(){
    fastio;
    cin>>n>>m;
    DSU d(n);
    for(int i=0;i<m;i++){
        int a,b; cin>>a>>b;
        d.join(a,b);
        cout<<d.components<<" "<<d.maxsz<<"\n";
    }
    return 0;
}