#include #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; using ll = long long ; using P = pair ; using pll = pair; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; struct Unionfind{ vector parents; vector sum; int n; Unionfind(int n):n(n),parents(n,-1),sum(n,0){ } int find(int x){ if(parents[x] < 0) return x; else return find(parents[x]); } void unite(int x,int y){ x = find(x); y = find(y); if(x==y) return; if(parents[x] > parents[x]) swap(x,y); parents[x] += parents[y]; parents[y] = x; sum[y] -= sum[x]; } int size(int x){ return -parents[find(x)]; } bool same(int x,int y){ return find(x)==find(y); } void add(int x,int a){ x = find(x); sum[x] += a; } int get(int x){ int res = 0; while(parents[x] >= 0){ res += sum[x]; x = parents[x]; } res += sum[x]; return res; } vector members(int x){ int root = find(x); vector member; for(int i=0;i