int pre[N];
int fnd(int x)
{
    int r=x;
    while(pre[r]!=r)
          r=pre[r];
    int i=x,j;
    while(i!=r)
    {
         j=pre[i];
         pre[i]=r;
         i=j;
    }
    return r;
}
void join(int x,int y)
{
    x=fnd(x),y=fnd(y);
    if(x!=y) pre[x]=y;
}