#pragma once
#include<vector>usingnamespacestd;structUnionFindEnumerate{vector<int>data,nxt;UnionFindEnumerate(intN):data(N,-1),nxt(N){for(inti=0;i<N;i++)nxt[i]=i;}intfind(intk){returndata[k]<0?k:data[k]=find(data[k]);}intunite(intx,inty){if((x=find(x))==(y=find(y)))returnfalse;if(data[x]>data[y])swap(x,y);data[x]+=data[y];data[y]=x;swap(nxt[x],nxt[y]);returntrue;}// f(x, y) : x に y をマージtemplate<typenameF>intunite(intx,inty,constF&f){if((x=find(x))==(y=find(y)))returnfalse;if(data[x]>data[y])swap(x,y);data[x]+=data[y];data[y]=x;f(x,y);swap(nxt[x],nxt[y]);returntrue;}intsize(intk){return-data[find(k)];}intsame(intx,inty){returnfind(x)==find(y);}vector<int>enumerate(inti){vector<int>res{i};for(intj=nxt[i];j!=i;j=nxt[j])res.push_back(j);returnres;}};
#line 2 "data-structure/union-find-enumerate.hpp"
#include<vector>usingnamespacestd;structUnionFindEnumerate{vector<int>data,nxt;UnionFindEnumerate(intN):data(N,-1),nxt(N){for(inti=0;i<N;i++)nxt[i]=i;}intfind(intk){returndata[k]<0?k:data[k]=find(data[k]);}intunite(intx,inty){if((x=find(x))==(y=find(y)))returnfalse;if(data[x]>data[y])swap(x,y);data[x]+=data[y];data[y]=x;swap(nxt[x],nxt[y]);returntrue;}// f(x, y) : x に y をマージtemplate<typenameF>intunite(intx,inty,constF&f){if((x=find(x))==(y=find(y)))returnfalse;if(data[x]>data[y])swap(x,y);data[x]+=data[y];data[y]=x;f(x,y);swap(nxt[x],nxt[y]);returntrue;}intsize(intk){return-data[find(k)];}intsame(intx,inty){returnfind(x)==find(y);}vector<int>enumerate(inti){vector<int>res{i};for(intj=nxt[i];j!=i;j=nxt[j])res.push_back(j);returnres;}};