import java.util.HashMap;
import java.util.List;
import java.util.Stack;

//并查集
public class d1 {
   public static class node<V>{
       V value;
       public node(V v){
           value=v;
       }
   }
   public static class uninoarray<V>{
       public HashMap<V,node> nodes;
       public HashMap<node,node> parents;
       public HashMap<node,Integer> sizemap;
       public uninoarray(List<V> list){
           for(V v:list){
               node<V> n=new node<>(v);
               nodes.put(v,n);
               parents.put(n,n);
               sizemap.put(n,1);
           }
       }
       public node<V> findfather(node<V> cur){
           //寻找头的同时，将路上的每个结点都设置一个头
           Stack<node<V>> s=new Stack<>();
           while(cur!=parents.get(cur)){
               s.add(cur);
               cur=parents.get(cur);
           }
           while(!s.isEmpty()){
               parents.put(s.pop(),cur);
           }
           return cur;
       }
       public boolean issame(V a,V b){//a，b是否在同一个集合
           if(!nodes.containsKey(a)||!nodes.containsKey(b)){
               return false;
           }
           return findfather(nodes.get(a))==findfather(nodes.get(b));
       }
       public boolean union(V a,V b){//将a，b划为一个集合
           //小集合挂在大集合下面
           if(!nodes.containsKey(a)||!nodes.containsKey(b)){
               return false;
           }
           node<V> f1=findfather(nodes.get(a));
           node<V>f2=findfather(nodes.get(b));
           if(f1!=f2){
               int len1=sizemap.get(f1);
               int len2=sizemap.get(f2);
               /* node<V> big=len1>=len2?f1:f2;
                node<V> small=big==f1?f2:f1;
               parents.put(small,big);
               sizemap.put(big,len1+len2);
               sizemap.remove(small);*/
               if(len1>=len2){
                   parents.put(f2,f1);
                   sizemap.put(f1,len1+len2);
                   sizemap.remove(f2);
                   return true;
               }else{
                   parents.put(f1,f2);
                   sizemap.put(f2,len1+len2);
                   sizemap.remove(f1);
                   return true;
               }
           }
           return false;
       }
   }
}