_depth[u] = 1;

         _rev_thread[u + 1] = u;

         _succ_num[u] = 1;

         _last_succ[u] = u;

         u = _parent[u];

         if (_succ_num[u] < _succ_num[v]) {

         v = _parent[v];

           u = _parent[u];

         } else {

           v = _parent[v];

         }

     // Update _thread and _parent vectors

     // Update the tree structure

     void updateThreadParent() {

     void updateTreeStructure() {

       int u;

       int u, w;

       int old_rev_thread = _rev_thread[u_out];

       int old_succ_num = _succ_num[u_out];

       int old_last_succ = _last_succ[u_out];

       // Handle the case when join and v_out coincide

       u = _last_succ[u_in];  // the last successor of u_in

       bool par_first = false;

       right = _thread[u];    // the node after it

       if (join == v_out) {

         for (u = join; u != u_in && u != v_in; u = _thread[u]) ;

       // Handle the case when old_rev_thread equals to v_in

         if (u == v_in) {

       // (it also means that join and v_out coincide)

           par_first = true;

       if (old_rev_thread == v_in) {

           while (_thread[u] != u_out) u = _thread[u];

         last = _thread[_last_succ[u_out]];

           first = u;

       } else {

         }

         last = _thread[v_in];

       }

       }

       // Find the last successor of u_in (u) and the node after it (right)

       // Update _thread and _parent along the stem nodes (i.e. the nodes

       // according to the thread index

       // between u_in and u_out, whose parent have to be changed)

       for (u = u_in; _depth[_thread[u]] > _depth[u_in]; u = _thread[u]) ;

       right = _thread[u];

       if (_thread[v_in] == u_out) {

         for (last = u; _depth[last] > _depth[u_out]; last = _thread[last]) ;

         if (last == u_out) last = _thread[last];

       }

       else last = _thread[v_in];

       // Update stem nodes

         _thread[u] = new_stem = _parent[stem];

         // Insert the next stem node into the thread list

         new_stem = _parent[stem];

         // Find the node just before the stem node (u) according to

         _thread[u] = new_stem;

         // the original thread index

         _dirty_revs.push_back(u);

         for (u = new_stem; _thread[u] != stem; u = _thread[u]) ;

         _thread[u] = right;

         // Remove the subtree of stem from the thread list

         w = _rev_thread[stem];

         // Change the parent node of stem and shift stem and par_stem nodes

         _thread[w] = right;

         _rev_thread[right] = w;

         // Change the parent node and shift stem nodes

         // Find the last successor of stem (u) and the node after it (right)

         // Update u and right

         // according to the thread index

         u = _last_succ[stem] == _last_succ[par_stem] ?

         for (u = stem; _depth[_thread[u]] > _depth[stem]; u = _thread[u]) ;

           _rev_thread[par_stem] : _last_succ[stem];

       _rev_thread[last] = u;

       if (join == v_out && par_first) {

       _last_succ[u_out] = u;

         if (first != v_in) _thread[first] = right;

       } else {

       // Remove the subtree of u_out from the thread list except for

         for (u = v_out; _thread[u] != u_out; u = _thread[u]) ;

       // the case when old_rev_thread equals to v_in

         _thread[u] = right;

       // (it also means that join and v_out coincide)

       }

       if (old_rev_thread != v_in) {

     }

         _thread[old_rev_thread] = right;

         _rev_thread[right] = old_rev_thread;

     // Update _pred and _forward vectors

       }

     void updatePredArc() {

       int u = u_out, v;

       // Update _rev_thread using the new _thread values

       for (int i = 0; i < int(_dirty_revs.size()); ++i) {

         u = _dirty_revs[i];

         _rev_thread[_thread[u]] = u;

       }

       // Update _pred, _forward, _last_succ and _succ_num for the

       // stem nodes from u_out to u_in

       int tmp_sc = 0, tmp_ls = _last_succ[u_out];

       u = u_out;

         v = _parent[u];

         w = _parent[u];

         _pred[u] = _pred[v];

         _pred[u] = _pred[w];

         _forward[u] = !_forward[v];

         _forward[u] = !_forward[w];

         u = v;

         tmp_sc += _succ_num[u] - _succ_num[w];

         _succ_num[u] = tmp_sc;

         _last_succ[w] = tmp_ls;

         u = w;

     }

       _succ_num[u_in] = old_succ_num;

     // Update _depth and _potential vectors

       // Set limits for updating _last_succ form v_in and v_out

     void updateDepthPotential() {

       // towards the root

       _depth[u_in] = _depth[v_in] + 1;

       int up_limit_in = -1;

       int up_limit_out = -1;

       if (_last_succ[join] == v_in) {

         up_limit_out = join;

       } else {

         up_limit_in = join;

       }

       // Update _last_succ from v_in towards the root

       for (u = v_in; u != up_limit_in && _last_succ[u] == v_in;

            u = _parent[u]) {

         _last_succ[u] = _last_succ[u_out];

       }

       // Update _last_succ from v_out towards the root

       if (join != old_rev_thread && v_in != old_rev_thread) {

         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;

              u = _parent[u]) {

           _last_succ[u] = old_rev_thread;

         }

       } else {

         for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ;

              u = _parent[u]) {

           _last_succ[u] = _last_succ[u_out];

         }

       }

       // Update _succ_num from v_in to join

       for (u = v_in; u != join; u = _parent[u]) {

         _succ_num[u] += old_succ_num;

       }

       // Update _succ_num from v_out to join

       for (u = v_out; u != join; u = _parent[u]) {

         _succ_num[u] -= old_succ_num;

       }

     }

     // Update potentials

     void updatePotential() {

       _pi[u_in] += sigma;

       if (_succ_num[u_in] > _node_num / 2) {

       for(int u = _thread[u_in]; _parent[u] != -1; u = _thread[u]) {

         // Update in the upper subtree (which contains the root)

         _depth[u] = _depth[_parent[u]] + 1;

         int before = _rev_thread[u_in];

         if (_depth[u] <= _depth[u_in]) break;

         int after = _thread[_last_succ[u_in]];

         _pi[u] += sigma;

         _thread[before] = after;

         _pi[_root] -= sigma;

         for (int u = _thread[_root]; u != _root; u = _thread[u]) {

           _pi[u] -= sigma;

         }

         _thread[before] = u_in;

       } else {

         // Update in the lower subtree (which has been moved)

         int end = _thread[_last_succ[u_in]];

         for (int u = u_in; u != end; u = _thread[u]) {

           _pi[u] += sigma;

         }

           updateThreadParent();

           updateTreeStructure();

           updatePredArc();

           updatePotential();

           updateDepthPotential();