#include #include #include #include #include #include #include #include #include #include #include #include #define vll vector #define vvvl vector #define vvl vector> #define VV(a, b, c, d) vector>(a, vector(b, c)) #define VVV(a, b, c, d) vector(a, vvl(b, vll (c, d))); #define re(c, b) for(ll c=0;c par, dep, sz, dat; UF(int n){ par.resize(n+1), dep.resize(n+1), sz.resize(n+1), dat.resize(n+1); init(n); } void init(int nu) { for(int iu=0;iu<=nu;iu++){ par[iu] = iu; dep[iu] = 0; sz[iu] = 1; dat[iu] = 0; } } int find(int xu){ if(par[xu] == xu) return xu; return find(par[xu]); } ll get(int xu){ if(par[xu]==xu) return dat[xu]; return dat[xu] + get(par[xu]); } void unite(int xu, int yu){ xu=find(xu); yu=find(yu); if(xu == yu) return; if(dep[xu] < dep[yu]){ sz[yu] += sz[xu]; par[xu] = yu; dat[xu] -= dat[yu]; }else{ par[yu] = xu; sz[xu] += sz[yu]; dat[yu] -= dat[xu]; if(dep[xu] == dep[yu]) dep[xu]++; } } bool same(int xu, int yu){ return find(xu) == find(yu);} int get_size(int x){return sz[find(x)];} }; int main(int argc, char const *argv[]) { ll n, q;scanf("%lld %lld", &n, &q); UF uf(n+1); for(int i=0;i