// M: max number of set
// id is in [0~M-1]
template<size_t M>
struct UF {
	int uf[M],sz[M];
	int n;
    int ns; // number of set
	void init(int n_) {
		n=ns=n_;
		for(int i=0;i<n;i++) uf[i]=i,sz[i]=1;
	}
	int find(int x) { return x==uf[x]?x:uf[x]=find(uf[x]); }
    bool same(int x,int y) { return find(x)==find(y); }
	bool merge(int x,int y) {
		x=find(x); y=find(y);
		if(x==y) return false;
		if(sz[x]>sz[y]) swap(x,y);
        sz[y]+=sz[x]; uf[x]=y; ns--;
		return true;
	}
};

    void show() {
        cerr<<"UnionFind:----------------------\n";
        cerr<<"id:";
        for(int i=0;i<n;i++) cerr<<'\t'<<i;
        cerr<<'\n';
        cerr<<"uf:";
        for(int i=0;i<n;i++) cerr<<'\t'<<uf[i];
        cerr<<'\n';
        cerr<<"sz:";
        for(int i=0;i<n;i++) cerr<<'\t'<<sz[i];
        cerr<<'\n';
        cerr<<"UnionFind:----------------------\n";
    }

// T must define +
// M: max number of set
// id is in [0~M-1]
template<typename T, size_t M, typename Op=plus<T>>
struct UF
{
    static Op op;
    int uf[M],sz[M];
    T info[M];
    int n;
    void init(int n_,T info_[]) {
        n=n_;
        for(int i=0;i<n;i++) uf[i]=i,sz[i]=1;
        for(int i=0;i<n;i++) info[i]=info_[i];
    }
    int find(int x) { return x==uf[x]?x:uf[x]=find(uf[x]); }
    bool merge(int x,int y) 
        x=find(x); y=find(y);
        if(x==y) return false;
        if(sz[x]>sz[y]) swap(x,y);
        sz[y]+=sz[x]; uf[x]=y;
        info[y]=op(info[x],info[y]);
        return true;
    }
    bool same(int x,int y) { return find(x)==find(y); }
    // get the info of the set contained x
    T& getinfo(int x) { return info[find(x)]; }
};

    void show() {
        cout<<"UnionFind:----------------------\n";
        cout<<"id:";
        for(int i=0;i<n;i++) cout<<'\t'<<i;
        cout<<'\n';
        cout<<"uf:";
        for(int i=0;i<n;i++) cout<<'\t'<<uf[i];
        cout<<'\n';
        cout<<"info:"
        for(int i=0;i<n;i++) cout<<'\t'<<info[i];
        cout<<'\n';
        cout<<"UnionFind:----------------------\n";
    }

// M: max number of set
// id is in [0~M-1]
template<size_t M>
struct UF
{
    typedef pair<int,int> PII;
	int uf[M],sz[M];
	int n;
    stack<PII> st;
	void init(int n_)
	{
		n=n_;
        while(!st.empty()) st.pop();
		for(int i=0;i<n;i++) uf[i]=i,sz[i]=1;
	}
	int find(int x)
	{
		return x==uf[x]?x:find(uf[x]);
	}
	bool merge(int x,int y)
	{
		x=find(x); y=find(y);
		if(x==y)
            return st.emplace(-1,-1),false;
		if(sz[x]>sz[y]) swap(x,y);
        sz[y]+=sz[x]; uf[x]=y; st.emplace(x,y); // x->y
		return true;
	}
    bool rollback() // check st.empty()
    {
        PII p=st.top(); st.pop();
        int x=p.first,y=p.second;
        if(x==-1) return false;
        sz[y]-=sz[x]; uf[x]=x;
        return true;
    }
};

    void show()
    {
        cout<<"UnionFind:----------------------\n";
        cout<<"id:";
        for(int i=0;i<n;i++) cout<<'\t'<<i;
        cout<<'\n';
        cout<<"uf:";
        for(int i=0;i<n;i++) cout<<'\t'<<uf[i];
        cout<<'\n';
        cout<<"UnionFind:----------------------\n";
    }

// M: max number of set
// id is in [0~M-1]
template<size_t M>
struct UF
{
    int uf[M],rk[M];
    int n;
    void init(int n_)
    {
        n=n_;
        for(int i=0;i<n;i++) uf[i]=i,rk[i]=0;
    }
    int find(int x)
    {
        return x==uf[x]?x:uf[x]=find(uf[x]);
    }
    bool merge(int x,int y)
    {
        x=find(x); y=find(y);
        if(x==y) return false;
        if(rk[x]<rk[y]) uf[x]=y;
        else if(rk[x]>rk[y]) uf[y]=x;
        else uf[y]=x,rk[x]++;
        return true;
    }
};

    void show()
    {
        cout<<"UnionFind:----------------------\n";
        cout<<"id:";
        for(int i=0;i<n;i++) cout<<'\t'<<i;
        cout<<'\n';
        cout<<"uf:";
        for(int i=0;i<n;i++) cout<<'\t'<<uf[i];
        cout<<'\n';
        cout<<"rk:";
        for(int i=0;i<n;i++) cout<<'\t'<<rk[i];
        cout<<'\n';
        cout<<"UnionFind:----------------------\n";
    }

// M: max number of set
// id is in [0~M-1]
template<size_t M>
struct UF
{
    int uf[M];
    int n;
    void init(int n_)
    {
        n=n_;
        for(int i=0;i<n;i++) uf[i]=i;
    }
    int find(int x)
    {
        return x==uf[x]?x:uf[x]=find(uf[x]);
    }
    bool merge(int x,int y)
    {
        x=find(x); y=find(y);
        if(x==y) return false;
        uf[x]=y;
        return true;
    }
};

    void show()
    {
        cout<<"UnionFind:----------------------\n";
        cout<<"id:";
        for(int i=0;i<n;i++) cout<<'\t'<<i;
        cout<<'\n';
        cout<<"uf:";
        for(int i=0;i<n;i++) cout<<'\t'<<uf[i];
        cout<<'\n';
        cout<<"UnionFind:----------------------\n";
    }