#include "dsu/UF_data.hpp"
template<typename T,typename F> class UF_data{ public: vector<int> data; vector<T>val; int sz; F merge; public: UF_data(int sz,F merge=F()):sz(sz),merge(merge){data.resize(sz,-1);val.resize(sz,T());} bool unite(int x,int y){ x=root(x);y=root(y); if(x==y)return 0; if(data[x]>data[y])swap(x,y); data[x]+=data[y]; data[y]=x; val[x]=merge(move(val[x]),move(val[y])); sz--; return 1; } inline void set(int x,const T&v){ x=root(x); val[x]=v; } template<typename G> void apply(int x,G g=G()){ x=root(x); g(val[x]); } inline T& get(int x){ return val[root(x)]; } inline int root(int x){return data[x]<0?x:data[x]=root(data[x]);} inline bool same(int x, int y){return root(x)==root(y);} inline int size(){return sz;} inline int size(int x){return -data[root(x)];} };
#line 1 "dsu/UF_data.hpp" template<typename T,typename F> class UF_data{ public: vector<int> data; vector<T>val; int sz; F merge; public: UF_data(int sz,F merge=F()):sz(sz),merge(merge){data.resize(sz,-1);val.resize(sz,T());} bool unite(int x,int y){ x=root(x);y=root(y); if(x==y)return 0; if(data[x]>data[y])swap(x,y); data[x]+=data[y]; data[y]=x; val[x]=merge(move(val[x]),move(val[y])); sz--; return 1; } inline void set(int x,const T&v){ x=root(x); val[x]=v; } template<typename G> void apply(int x,G g=G()){ x=root(x); g(val[x]); } inline T& get(int x){ return val[root(x)]; } inline int root(int x){return data[x]<0?x:data[x]=root(data[x]);} inline bool same(int x, int y){return root(x)==root(y);} inline int size(){return sz;} inline int size(int x){return -data[root(x)];} };