TopTree(WIP)
(graph_tree/top_tree.hpp)

/**
 * @brief TopTree(WIP)
 */

template<typename T,typename E>
class top_tree{
	struct node;
	using np=node*;
	struct cluster{
		bool is_compress,is_edge,guarded;
		int l,r;
		T key=et;
		np ch[3]={nullptr,nullptr,nullptr};
		np p=nullptr;
		cluster(){}
		cluster(int l,int r,bool is_compress,bool is_edge):l(l),r(r),is_compress(is_compress),is_edge(is_edge){}
        bool is_root(){
            return !p||p->guarded||(p->ch[0]!=this&&p->ch[1]!=this);
        }
	};
	np root=nullptr;
	void join(np p,np t,int i){
		if(t)t->p=p;
		if(p)p->ch[i]=t,update(p);
	}
	//左右の子を入れ替える
	void swap(np t){
		swap(t->l,t->r);
		swap(t->ch[0],t->ch[1]);
		toggle(t->ch[0]);toggle(t->ch[1]);
	}
    void update(np t){

    }
    void rot(np t,bool b){
        np x=t->p,y=x->p;
        if((x->ch[1-b]=t->ch[b]))t->ch[b]->p=x;
        t->ch[b]=x,x->p=t;
        update(x);update(t);
        if((t->p=y)){
            if(y->ch[0]==x)y->ch[0]=t;
            if(y->ch[1]==x)y->ch[1]=t;
            update(y);
        }
    }
    void splay(np t){
        push(t);
        while(!t->is_root()){
            np q=t->p;
            if(q->is_root()){
                push(q),push(t);
                rot(t,q->ch[0]==t);
            }else{
                np r=q->p;
                push(r),push(q),push(t);
                bool b=r->ch[0]==q;
                if(q->ch[1-b]==t)rot(q,b),rot(t,b);
                else rot(t,1-b),rot(t,b);
            }
        }
    }
	void push(np t){
		
    }
	void toggle(np t){

	}
	void splice(np s,np t,bool b){
		if(!b){
			join(s->p,t,(s->p->ch[1]==s)+2*(s->p->ch[2]==s));
			join(t->p,s,(t->p->ch[1]==t)+2*(t->p->ch[2]==t));
		}else{
			toggle(s);toggle(t);
			join(s->p,t,(s->p->ch[1]==s)+2*(s->p->ch[2]==s));
			join(t->p,s,(t->p->ch[1]==t)+2*(t->p->ch[2]==t));
		}
	}
	void expose(np t){
		while(1){
			splay(t);
			if(!t->p)return;
			np n;
			if(t->p->is_compress){
				n=t->p;
			}else{
				np s=t->p;
				splay(s);
				n=s->p;
			}
			bool b=n->p&&n->p->guarded;
			splice(t,n->ch[b],b);
			if(t->is_edge)t=n;
		}
	}
	void soft_expose(np s,np t){
		expose(s);
		if(s!=t){
			guard(s,1);
			expose(t);
			guard(s,0);
		}
		if(s->ch[0]=t){
			swap(s);
		}
	}
	np handle(int s){

	}
	void link(int s,int t){
		np v=handle(s),w=handle(t);
		if(w){
			expose(w);
			if(v->l!=t&&v->r!=t){
				np rp=new node(-1,-1,0,0);
				np q=new node(s,t,0,1);
				join(rp,v->ch[2],0);
				join(rp,v->ch[0],1);
				join(v,q,0);
				join(v,rp,2);
			}else{
				if(v->r==t)swap(v);
				np p=new node(s,v->r,1,0);
				np q=new node(s,t,0,1);
				join(p,q,0);
				join(p,v,1);
				v=p;
			}
		}else{
			v=new node(s,t,0,1);
		}
		
	}
	void cut(){

	}
};

#line 1 "graph_tree/top_tree.hpp"
/**
 * @brief TopTree(WIP)
 */

template<typename T,typename E>
class top_tree{
	struct node;
	using np=node*;
	struct cluster{
		bool is_compress,is_edge,guarded;
		int l,r;
		T key=et;
		np ch[3]={nullptr,nullptr,nullptr};
		np p=nullptr;
		cluster(){}
		cluster(int l,int r,bool is_compress,bool is_edge):l(l),r(r),is_compress(is_compress),is_edge(is_edge){}
        bool is_root(){
            return !p||p->guarded||(p->ch[0]!=this&&p->ch[1]!=this);
        }
	};
	np root=nullptr;
	void join(np p,np t,int i){
		if(t)t->p=p;
		if(p)p->ch[i]=t,update(p);
	}
	//左右の子を入れ替える
	void swap(np t){
		swap(t->l,t->r);
		swap(t->ch[0],t->ch[1]);
		toggle(t->ch[0]);toggle(t->ch[1]);
	}
    void update(np t){

    }
    void rot(np t,bool b){
        np x=t->p,y=x->p;
        if((x->ch[1-b]=t->ch[b]))t->ch[b]->p=x;
        t->ch[b]=x,x->p=t;
        update(x);update(t);
        if((t->p=y)){
            if(y->ch[0]==x)y->ch[0]=t;
            if(y->ch[1]==x)y->ch[1]=t;
            update(y);
        }
    }
    void splay(np t){
        push(t);
        while(!t->is_root()){
            np q=t->p;
            if(q->is_root()){
                push(q),push(t);
                rot(t,q->ch[0]==t);
            }else{
                np r=q->p;
                push(r),push(q),push(t);
                bool b=r->ch[0]==q;
                if(q->ch[1-b]==t)rot(q,b),rot(t,b);
                else rot(t,1-b),rot(t,b);
            }
        }
    }
	void push(np t){
		
    }
	void toggle(np t){

	}
	void splice(np s,np t,bool b){
		if(!b){
			join(s->p,t,(s->p->ch[1]==s)+2*(s->p->ch[2]==s));
			join(t->p,s,(t->p->ch[1]==t)+2*(t->p->ch[2]==t));
		}else{
			toggle(s);toggle(t);
			join(s->p,t,(s->p->ch[1]==s)+2*(s->p->ch[2]==s));
			join(t->p,s,(t->p->ch[1]==t)+2*(t->p->ch[2]==t));
		}
	}
	void expose(np t){
		while(1){
			splay(t);
			if(!t->p)return;
			np n;
			if(t->p->is_compress){
				n=t->p;
			}else{
				np s=t->p;
				splay(s);
				n=s->p;
			}
			bool b=n->p&&n->p->guarded;
			splice(t,n->ch[b],b);
			if(t->is_edge)t=n;
		}
	}
	void soft_expose(np s,np t){
		expose(s);
		if(s!=t){
			guard(s,1);
			expose(t);
			guard(s,0);
		}
		if(s->ch[0]=t){
			swap(s);
		}
	}
	np handle(int s){

	}
	void link(int s,int t){
		np v=handle(s),w=handle(t);
		if(w){
			expose(w);
			if(v->l!=t&&v->r!=t){
				np rp=new node(-1,-1,0,0);
				np q=new node(s,t,0,1);
				join(rp,v->ch[2],0);
				join(rp,v->ch[0],1);
				join(v,q,0);
				join(v,rp,2);
			}else{
				if(v->r==t)swap(v);
				np p=new node(s,v->r,1,0);
				np q=new node(s,t,0,1);
				join(p,q,0);
				join(p,v,1);
				v=p;
			}
		}else{
			v=new node(s,t,0,1);
		}
		
	}
	void cut(){

	}
};