#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1000005;
int father[maxn];
/*常规并查集模板*/ 
void make_set(int x)
{
    for(int i=1;i<=x;i++)
    {
        father[i]=i;
    }
}
int find(int x)                        //递归法路径压缩 
{
    if(x!=father[x])
    {
        father[x]=find(father[x]);    
    }
    return father[x];
}
void join(int x,int y)
{
    int p,q;
    p=find(x);
    q=find(y);
    if(p!=q)
    {
        father[p]=q;
    }
} 

/*树的深度优化，按秩序合并*/
int rank[maxn];        //初始化为0，代表树的初始深度为0 
void join_2(int x,int y)
{
    int a,b;
    a=find(x);
    b=find(y);
    if(a==b)
    {
        return ;    //两个元素在一个集合的话直接退出    
    } 
    if(rank[a]<rank[b])
    {
        father[a]=b;    
    } 
    else 
    {
        father[b]=a;
        if(rank[x]==rank[y])
        {
            rank[x]++;    
        }    
    }
}

/*非递归法寻找祖宗*/
//使单个节点直接指向父亲，路径没有压缩 
int find(int x)
{
    int x1 = x;
    while(pre[x]!=x)x = pre[x];            //循环法寻找祖先节点 
    if(pre[x1]!=x) pre[x1] = x;            //找到它的祖先节点 
    return x;
} 
/*非递归法寻找祖先，路径压缩算法*/ 
int find(int x)             //查找根节点
{ 
    int r=x;
    while ( pre[r ] != r )   //返回根节点 r
          r=pre[r ];
    int i=x , j ;
    while( i != r )         //路径压缩
    {
         j = pre[ i ]; // 在改变上级之前用临时变量  j 记录下他的值 
         pre[ i ]= r ; //把上级改为根节点
         i=j;
    }
    return r ;
}
//循环法，路径不压缩
int find(int x)             //查找根节点
{ 
    int r=x;
    while ( pre[r ] != r )   //返回根节点 r
          r=pre[r ];
    return r ;
}