public class DisjointSet{
        public int[] Array;
        
        public DisjointSet(int[] array){
            Array = array;
        }
        
        public int FindParent(int index){
            if(Array[index] == -1){
                return index;
            }
            
            return FindParent(Array[index]);
        }
        
        public void Union(int el1, int el2){
            var el1Parent = FindParent(el1);
            var el2Parent = FindParent(el2);
            if(el1Parent != el2Parent){
                Array[el1Parent] = el2Parent;
            }
        }
    }
    
    public class DisjointSetOptimization{
        public int[] Array;
        private int[] _rank;
        
        public DisjointSetOptimization(int[] array){
            Array = array;
            _rank = Enumerable.Repeat(1, array.Length).ToArray();
        }
        
        public int FindParent(int index){
            if(Array[index] == -1){
                return index;
            }
            
            return Array[index] = FindParent(Array[index]);
        }
        
        public void Union(int el1, int el2){
            var el1Parent = FindParent(el1);
            var el2Parent = FindParent(el2);
            if(el1Parent == el2Parent){
                return;
            }
            
            if(_rank[el1Parent] > _rank[el2Parent]){
                Array[el2Parent] = el1Parent;
            } else if(_rank[el1Parent] < _rank[el2Parent]){
                Array[el1Parent] = el2Parent;
            } else {
                Array[el2Parent] = el1Parent;
                _rank[el1Parent]++;
            }
        }
    }