/**

   /// \brief A \e Union-Find data structure implementation

    * \brief A \e Union-Find data structure implementation

   ///

    *

   /// The class implements the \e Union-Find data structure. 

    * The class implements the \e Union-Find data structure. 

   /// The union operation uses rank heuristic, while

    * The union operation uses rank heuristic, while

   /// the find operation uses path compression.

    * the find operation uses path compression.

   /// This is a very simple but efficient implementation, providing 

    * This is a very simple but efficient implementation, providing 

   /// only four methods: join (union), find, insert and size.

    * only four methods: join (union), find, insert and size.

   /// For more features see the \ref UnionFindEnum class.

    * For more features see the \ref UnionFindEnum class.

   ///

    *

   /// It is primarily used in Kruskal algorithm for finding minimal

    * It is primarily used in Kruskal algorithm for finding minimal

   /// cost spanning tree in a graph.

    * cost spanning tree in a graph.

   /// \sa kruskal()

    * \sa kruskal()

   ///

    *

   /// \pre You need to add all the elements by the \ref insert()

    * \pre The elements are automatically added only if the map 

   /// method.  

    * given to the constructor was filled with -1's. Otherwise you

   template <typename Item, typename ItemIntMap>

    * need to add all the elements by the \ref insert() method.

    * \bug It is not clear what the constructor parameter is used for.

    */

   template <typename T, typename TIntMap>

     typedef T ElementType;

     typedef Item ElementType;

     typedef std::pair<int,int> PairType;

     std::vector<PairType> data;

     // If the items vector stores negative value for an item then

     TIntMap& map;

     // that item is root item and it has -items[it] component size.

     // Else the items[it] contains the index of the parent.

     std::vector<int> items;

     ItemIntMap& index;

     bool rep(int idx) const {

       return items[idx] < 0;

     }

     int repIndex(int idx) const {

       int k = idx;

       while (!rep(k)) {

         k = items[k] ;

       }

       while (idx != k) {

         int next = items[idx];

         const_cast<int&>(items[idx]) = k;

         idx = next;

       }

       return k;

     }

     UnionFind(TIntMap& m) : map(m) {}

     /// \brief Constructor

     /**

     ///

      * \brief Returns the index of the element's component.

     /// Constructor of the UnionFind class. You should give an item to

      *

     /// integer map which will be used from the data structure. If you

      * The method returns the index of the element's component.

     /// modify directly this map that may cause segmentation fault,

      * This is an integer between zero and the number of inserted elements.

     /// invalid data structure, or infinite loop when you use again

      */

     /// the union-find.

     UnionFind(ItemIntMap& m) : index(m) {}

     int find(T a)

     {

     /// \brief Returns the index of the element's component.

       int comp0 = map[a];

     ///

       if (comp0 < 0) {

     /// The method returns the index of the element's component.

 	return insert(a);

     /// This is an integer between zero and the number of inserted elements.

       }

     ///

       int comp = comp0;

     int find(const Item& a) {

       int next;

       return repIndex(index[a]);

       while ( (next = data[comp].first) != comp) {

     }

 	comp = next;

       }

     /// \brief Inserts a new element into the structure.

       while ( (next = data[comp0].first) != comp) {

     ///

 	data[comp0].first = comp;

     /// This method inserts a new element into the data structure. 

 	comp0 = next;

     ///

       }

     /// The method returns the index of the new component.

     int insert(const Item& a) {

       return comp;

       int n = items.size();

     }

       items.push_back(-1);

       index.set(a,n);

     /**

      * \brief Inserts a new element into the structure.

      *

      * This method inserts a new element into the data structure. 

      *

      * It is not required to use this method:

      * if the map given to the constructor was filled 

      * with -1's then it is called automatically

      * on the first \ref find or \ref join.

      *

      * The method returns the index of the new component.

      */

     int insert(T a)

     {

       int n = data.size();

       data.push_back(std::make_pair(n, 1));

       map.set(a,n);

     /**

     /// \brief Joining the components of element \e a and element \e b.

      * \brief Joining the components of element \e a and element \e b.

     ///

      *

     /// This is the \e union operation of the Union-Find structure. 

      * This is the \e union operation of the Union-Find structure. 

     /// Joins the component of element \e a and component of

      * Joins the component of element \e a and component of

     /// element \e b. If \e a and \e b are in the same component then

      * element \e b. If \e a and \e b are in the same component then

     /// it returns false otherwise it returns true.

      * it returns false otherwise it returns true.

     bool join(const Item& a, const Item& b) {

      */

       int ka = repIndex(index[a]);

       int kb = repIndex(index[b]);

     bool join(T a, T b)

     {

       if ( ka == kb ) 

       int ca = find(a);

       int cb = find(b);

       if ( ca == cb ) 

       if ( data[ca].second > data[cb].second ) {

       if (items[ka] < items[kb]) {

 	data[cb].first = ca;

 	items[ka] += items[kb];

 	data[ca].second += data[cb].second;

 	items[kb] = ka;

       }

       } else {

       else {

 	items[kb] += items[ka];

 	data[ca].first = cb;

 	items[ka] = kb;

 	data[cb].second += data[ca].second;

     /**

     /// \brief Returns the size of the component of element \e a.

      * \brief Returns the size of the component of element \e a.

     ///

      *

     /// Returns the size of the component of element \e a.

      * Returns the size of the component of element \e a.

     int size(const Item& a) {

      */

       int k = repIndex(index[a]);

       return - items[k];

     int size(T a)

     {

       int ca = find(a);

       return data[ca].second;

   /// \brief A \e Union-Find data structure implementation which

   /// is able to enumerate the components.

   /*******************************************************/

   ///

   /// The class implements a \e Union-Find data structure

   /// which is able to enumerate the components and the items in

 #ifdef DEVELOPMENT_DOCS

   /// a component. If you don't need this feature then perhaps it's

   /// better to use the \ref UnionFind class which is more efficient.

   /**

   ///

    * \brief The auxiliary class for the \ref UnionFindEnum class.

   /// The union operation uses rank heuristic, while

    *

   /// the find operation uses path compression.

    * In the \ref UnionFindEnum class all components are represented as

   ///

    * a std::list. 

   /// \pre You need to add all the elements by the \ref insert()

    * Items of these lists are UnionFindEnumItem structures.

   /// method.

    *

   ///

    * The class has four fields:

   template <typename _Item, typename _ItemIntMap>

    *  - T me - the actual element 

   class UnionFindEnum {

    *  - IIter parent - the parent of the element in the union-find structure

   public:

    *  - int size - the size of the component of the element. 

    *            Only valid if the element

     typedef _Item Item;

    *            is the leader of the component.

     typedef _ItemIntMap ItemIntMap;

    *  - CIter my_class - pointer into the list of components 

    *            pointing to the component of the element.

   private:

    *            Only valid if the element is the leader of the component.

    */

     // If the parent stores negative value for an item then that item

     // is root item and it has -items[it].parent component size.  Else

 #endif

     // the items[it].parent contains the index of the parent.

     //

   template <typename T>

     // The \c nextItem and \c prevItem provides the double-linked

   struct UnionFindEnumItem {

     // cyclic list of one component's items. The \c prevClass and

     // \c nextClass gives the double linked list of the representant

     typedef std::list<UnionFindEnumItem> ItemList;

     // items. 

     typedef std::list<ItemList> ClassList;

     struct ItemT {

     typedef typename ItemList::iterator IIter;

       int parent;

     typedef typename ClassList::iterator CIter;

       Item item;

     T me;

       int nextItem, prevItem;

     IIter parent;

       int nextClass, prevClass;

     int size;

     };

     CIter my_class;

     std::vector<ItemT> items;

     UnionFindEnumItem() {}

     ItemIntMap& index;

     UnionFindEnumItem(const T &_me, CIter _my_class): 

       me(_me), size(1), my_class(_my_class) {}

     int firstClass;

     bool rep(int idx) const {

       return items[idx].parent < 0;

     }

     int repIndex(int idx) const {

       int k = idx;

       while (!rep(k)) {

         k = items[k].parent;

       }

       while (idx != k) {

         int next = items[idx].parent;

         const_cast<int&>(items[idx].parent) = k;

         idx = next;

       }

       return k;

     }

     void unlaceClass(int k) {

       if (items[k].prevClass != -1) {

         items[items[k].prevClass].nextClass = items[k].nextClass;

       } else {

         firstClass = items[k].nextClass;

       }

       if (items[k].nextClass != -1) {

         items[items[k].nextClass].prevClass = items[k].prevClass;

       }

     } 

     void spliceItems(int ak, int bk) {

       items[items[ak].prevItem].nextItem = bk;

       items[items[bk].prevItem].nextItem = ak;

       int tmp = items[ak].prevItem;

       items[ak].prevItem = items[bk].prevItem;

       items[bk].prevItem = tmp;

     }

   public:

     UnionFindEnum(ItemIntMap& _index) 

       : items(), index(_index), firstClass(-1) {}

     /// \brief Inserts the given element into a new component.

     ///

     /// This method creates a new component consisting only of the

     /// given element.

     ///

     void insert(const Item& item) {

       ItemT t;

       int idx = items.size();

       index.set(item, idx);

       t.nextItem = idx;

       t.prevItem = idx;

       t.item = item;

       t.parent = -1;

       t.nextClass = firstClass;

       if (firstClass != -1) {

         items[firstClass].prevClass = idx;

       }

       t.prevClass = -1;

       firstClass = idx;

       items.push_back(t);

     }

     /// \brief Inserts the given element into the component of the others.

     ///

     /// This methods inserts the element \e a into the component of the

     /// element \e comp. 

     void insert(const Item& item, const Item& comp) {

       int k = repIndex(index[comp]);

       ItemT t;

       int idx = items.size();

       index.set(item, idx);

       t.prevItem = k;

       t.nextItem = items[k].nextItem;

       items[items[k].nextItem].prevItem = idx;

       items[k].nextItem = idx;

       t.item = item;

       t.parent = k;

       --items[k].parent;

       items.push_back(t);

     }

     /// \brief Finds the leader of the component of the given element.

     ///

     /// The method returns the leader of the component of the given element.

     const Item& find(const Item &item) const {

       return items[repIndex(index[item])].item;

     }

     /// \brief Joining the component of element \e a and element \e b.

     ///

     /// This is the \e union operation of the Union-Find structure. 

     /// Joins the component of element \e a and component of

     /// element \e b. If \e a and \e b are in the same component then

     /// returns false else returns true.

     bool join(const Item& a, const Item& b) {

       int ak = repIndex(index[a]);

       int bk = repIndex(index[b]);

       if (ak == bk) {

 	return false;

       }

       if ( items[ak].parent < items[bk].parent ) {

         unlaceClass(bk);

         items[ak].parent += items[bk].parent;

 	items[bk].parent = ak;

       } else {

         unlaceClass(bk);

         items[bk].parent += items[ak].parent;

 	items[ak].parent = bk;

       }

       spliceItems(ak, bk);

       return true;

     }

     /// \brief Returns the size of the component of element \e a.

     ///

     /// Returns the size of the component of element \e a.

     int size(const Item &item) const {

       return - items[repIndex(index[item])].parent;

     }

     /// \brief Splits up the component of the element. 

     ///

     /// Splitting the component of the element into sigleton

     /// components (component of size one).

     void split(const Item &item) {

       int k = repIndex(index[item]);

       int idx = items[k].nextItem;

       while (idx != k) {

         int next = items[idx].nextItem;

         items[idx].parent = -1;

         items[idx].prevItem = idx;

         items[idx].nextItem = idx;

         items[idx].nextClass = firstClass;

         items[firstClass].prevClass = idx;

         firstClass = idx;

         idx = next;

       }

       items[idx].parent = -1;

       items[idx].prevItem = idx;

       items[idx].nextItem = idx;

       items[firstClass].prevClass = -1;

     }

     /// \brief Sets the given element to the leader element of its component.

     ///

     /// Sets the given element to the leader element of its component.

     void makeRep(const Item &item) {

       int nk = index[item];

       int k = repIndex(nk);

       if (nk == k) return;

       if (items[k].prevClass != -1) {

         items[items[k].prevClass].nextClass = nk;

       } else {

         firstClass = nk;

       }

       if (items[k].nextClass != -1) {

         items[items[k].nextClass].prevClass = nk;

       }

       int idx = items[k].nextItem;

       while (idx != k) {

         items[idx].parent = nk;

         idx = items[idx].nextItem;

       }

       items[nk].parent = items[k].parent;

       items[k].parent = nk;

     }

     /// \brief Removes the given element from the structure.

     ///

     /// Removes the element from its component and if the component becomes

     /// empty then removes that component from the component list.

     ///

     /// \warning It is an error to remove an element which is not in

     /// the structure.

     void erase(const Item &item) {

       int idx = index[item];

       if (rep(idx)) {

         int k = idx;

         if (items[k].parent == -1) {

           unlaceClass(idx);

           return;

         } else {

           int nk = items[k].nextItem;

           if (items[k].prevClass != -1) {

             items[items[k].prevClass].nextClass = nk;

           } else {

             firstClass = nk;

           }

           if (items[k].nextClass != -1) {

             items[items[k].nextClass].prevClass = nk;

           }

           int idx = items[k].nextItem;

           while (idx != k) {

             items[idx].parent = nk;

             idx = items[idx].nextItem;

           }

           items[nk].parent = items[k].parent + 1;

         }

       } else {

         int k = repIndex(idx);

         idx = items[k].nextItem;

         while (idx != k) {

           items[idx].parent = k;

           idx = items[idx].nextItem;

         }

         ++items[k].parent;

       }

       idx = index[item];      

       items[items[idx].prevItem].nextItem = items[idx].nextItem;

       items[items[idx].nextItem].prevItem = items[idx].prevItem;

     }    

     /// \brief Moves the given element to another component.

     ///

     /// This method moves the element \e a from its component

     /// to the component of \e comp.

     /// If \e a and \e comp are in the same component then

     /// it returns false otherwise it returns true.

     bool move(const Item &item, const Item &comp) {

       if (repIndex(index[item]) == repIndex(index[comp])) return false;

       erase(item);

       insert(item, comp);

       return true;

     }

     /// \brief Removes the component of the given element from the structure.

     ///

     /// Removes the component of the given element from the structure.

     ///

     /// \warning It is an error to give an element which is not in the

     /// structure.

     void eraseClass(const Item &item) {

       unlaceClass(repIndex(index[item]));

     }

     /// \brief Lemon style iterator for the representant items.

     ///

     /// ClassIt is a lemon style iterator for the components. It iterates

     /// on the representant items of the classes.

     class ClassIt {

     public:

       /// \brief Constructor of the iterator

       ///

       /// Constructor of the iterator

       ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {

         idx = unionFind->firstClass;

       }

       /// \brief Constructor to get invalid iterator

       ///

       /// Constructor to get invalid iterator

       ClassIt(Invalid) : unionFind(0), idx(-1) {}

       /// \brief Increment operator

       ///

       /// It steps to the next representant item.

       ClassIt& operator++() {

         idx = unionFind->items[idx].nextClass;

         return *this;

       }

       /// \brief Conversion operator

       ///

       /// It converts the iterator to the current representant item.

       operator const Item&() const {

         return unionFind->items[idx].item;

       }

       /// \brief Equality operator

       ///

       /// Equality operator

       bool operator==(const ClassIt& i) { 

         return i.idx == idx;

       }

       /// \brief Inequality operator

       ///

       /// Inequality operator

       bool operator!=(const ClassIt& i) { 

         return i.idx != idx;

       }

     private:

       const UnionFindEnum* unionFind;

       int idx;

     };

     /// \brief Lemon style iterator for the items of a component.

     ///

     /// ClassIt is a lemon style iterator for the components. It iterates

     /// on the items of a class. By example if you want to iterate on

     /// each items of each classes then you may write the next code.

     ///\code

     /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {

     ///   std::cout << "Class: ";

     ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {

     ///     std::cout << toString(iit) << ' ' << std::endl;

     ///   }

     ///   std::cout << std::endl;

     /// }

     ///\endcode

     class ItemIt {

     public:

       /// \brief Constructor of the iterator

       ///

       /// Constructor of the iterator. The iterator iterates

       /// on the class of the \c item.

       ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {

         idx = unionFind->repIndex(unionFind->index[item]);

       }

       /// \brief Constructor to get invalid iterator

       ///

       /// Constructor to get invalid iterator

       ItemIt(Invalid) : unionFind(0), idx(-1) {}

       /// \brief Increment operator

       ///

       /// It steps to the next item in the class.

       ItemIt& operator++() {

         idx = unionFind->items[idx].nextItem;

         if (unionFind->rep(idx)) idx = -1;

         return *this;

       }

       /// \brief Conversion operator

       ///

       /// It converts the iterator to the current item.

       operator const Item&() const {

         return unionFind->items[idx].item;

       }

       /// \brief Equality operator

       ///

       /// Equality operator

       bool operator==(const ItemIt& i) { 

         return i.idx == idx;

       }

       /// \brief Inequality operator

       ///

       /// Inequality operator

       bool operator!=(const ItemIt& i) { 

         return i.idx != idx;

       }

     private:

       const UnionFindEnum* unionFind;

       int idx;

     };