#include<cstdio>
#include<algorithm>
#include<vector>

const int NIL = -1;

class LCT {
 private:
  struct Node {
    Node() : fa(NIL), rev(false) {
      son[0] = NIL;
      son[1] = NIL;
    }
    int fa;
    int son[2];
    bool rev;
    //anything you want
  };
  std::vector<Node> node;
  int isChild(int now) {
    if(node[now].fa == -1) return -1;
    if(node[node[now].fa].son[0] == now) return 0;
    if(node[node[now].fa].son[1] == now) return 1; 
    return -1;
  }
  void pushdown(int now) {
    if(now == -1) return;
    if(!node[now].rev) return; 
    node[now].rev = false;
    if(node[now].son[0] != NIL) {
      std::swap(node[node[now].son[0]].son[0], node[node[now].son[0]].son[1]);
      node[node[now].son[0]].rev = !node[node[now].son[0]].rev;
    }
    if(node[now].son[1] != NIL) {
      std::swap(node[node[now].son[1]].son[0], node[node[now].son[1]].son[1]);
      node[node[now].son[1]].rev = !node[node[now].son[1]].rev;
    }
    return;
  }
  void update(int now) {
    //anything you want
    if(node[now].son[0] != NIL) {

    }
    if(node[now].son[1] != NIL) {

    }
    return;
  }
  void rotate(int now) {
    if(isChild(now) == -1) return;
    int fa = node[now].fa;
    pushdown(fa);
    pushdown(now);
    int x = isChild(now);
    int y = isChild(fa);
    if(~y) {
      node[node[fa].fa].son[y] = now;
    }
    node[fa].son[x] = node[now].son[x ^ 1];
    node[now].son[x ^ 1] = fa;

    node[now].fa = node[fa].fa;
    node[fa].fa = now;
    if(~node[fa].son[x]) node[node[fa].son[x]].fa = fa;
    update(fa);
    update(now);
    return;
  }
  void splay(int now) {
    if(now == -1) return;
    pushdown(now);
    while(~isChild(now)) {
      if(isChild(node[now].fa) == isChild(now)) rotate(node[now].fa);
      rotate(now);
    }
    return;
  }
  void access(int now) {
    int last = NIL;
    while(~now) {
      splay(now);
      node[now].son[1] = last;
      update(now);
      last = now;
      now = node[now].fa;
    }
  }
  void reverse(int now) {
    std::swap(node[now].son[0], node[now].son[1]);
    node[now].rev = !node[now].rev;
  }
  void makeRoot(int now) {
    access(now);
    splay(now);
    reverse(now);
  }
  int findRoot(int now) {
    access(now);
    while(now != NIL) {
      pushdown(now);
      if(node[now].son[0] == NIL) break;
      now = node[now].son[0];
    }
    return now;
  }
  void split(int a, int b) {
    makeRoot(a);
    access(b);
    splay(b);
  }
 public:
  int newNode() {
    node.push_back(Node());
    return node.size() - 1;
  }
  void cut(int a, int b) {
    split(a, b);
    if(node[b].son[0] != a || node[a].son[1] != NIL) return;
    node[b].son[0] = NIL;
    node[a].fa = NIL;
    update(b);
  }
  void link(int a, int b) {
    makeRoot(a);
    if(findRoot(b) == a) return;
    node[a].fa = b;
  }
  //other functions you want
};