/*
	LCT模板，支持路径上的值的修改和查询。不支持对子树操作。
	
	除了0号结点，其他节点都能使用，清空时memset f数组就行了。

	函数中有//的地方是你有可能需要写代码的地方。

	维护的值必须都在点上，如果值在边上，可以把边看成额外的点。
	例如：link(边id,x) link(边id,y)
	
	struct sf里面的l,r,par,rev是必须的信息，如果需要维护其他的
	内容，你可以自行添加。如果节点x的左子节点(f[x].l)或右子节点
	f[x].r)是0，说明子节点不存在，在使用下面说到的push和update
	函数的时候要注意处理。

	如果自己使用不是模板里的函数对splay进行遍历或者其他操作时，
	不要忘记push和update函数的使用。
	
	常用的函数说明：
	
	push(x)是将维护的信息下推给自己的左右儿子，可以参考线段树。
	
	update(x)是维护当前结点信息，用例：
		f[x].mx=max(f[f[x].l].mx,f[f[x].r].mx);
		f[x].mx=max(f[x].mx,f[x].x);
		这样就维护了路径上最大值的信息。
	
	link(x,y)是将x和y连接起来，连接之前需要保证x和y属于不同的树。
	
	cut(x,y)是将(x,y)这条边砍断，砍断之前需要保证这条边存在。
	
	isconnect(x,y)是检查x和y是否属于同一棵树。
	
	query(x,y)是查询x到y这条路径上的信息，用例：
		return f[y].mx;
		这样就返回了路径上的最大值。
	
	change(x,y)是修改x到y这条路径上的值，用例：
		f[y].xv+=v;
		这样就给路径上的值都加上了v。

	不常用的函数说明：

	isroot(x)是判断x节点是否为splay的根。

	rotate(x)是把x节点旋转到splay上他的父亲节点的位置。

	splay(x)是把x节点旋转到splay的根节点上。

	access(x)是把x到x所在树的根路径上的所有节点组成一棵splay，
	并且把x节点旋转到splay的根节点上。

	makeroot(x)是把x节点变成他所在的树的根。
*/

#include<bits/stdc++.h>
#define MAXN 210000
using namespace std;

struct sf {
	int l,r,par,rev;
} f[MAXN];

bool isroot(int x) {
	return f[f[x].par].l!=x && f[f[x].par].r!=x;
}

void push(int x) {
	if (f[x].rev) {
		f[f[x].l].rev^=1;
		f[f[x].r].rev^=1;
		swap(f[x].l,f[x].r);
		f[x].rev=0;
	}
	//
}

void update(int x) {
	//
}

void rotate(int x) {
	int y=f[x].par,z=f[y].par;
	push(y);push(x);
	if (f[y].l==x) f[f[y].l=f[x].r].par=y,f[x].r=y;
	else f[f[y].r=f[x].l].par=y,f[x].l=y;
	if (f[z].l==y) f[z].l=x;
	if (f[z].r==y) f[z].r=x;
	f[f[y].par=x].par=z;
	update(y);
}

void splay(int x) {
	push(x);
	for (;!isroot(x);rotate(x)) {
		int y=f[x].par,z=f[y].par;
		if (!isroot(y)) rotate(f[z].l==y^f[y].l==x?x:y);
	}
	update(x);
}

void access(int x) {
	for(int t=0,y=x;y;y=f[y].par) splay(y),f[y].r=t,update(t=y);
	splay(x);
}

void makeroot(int x) {
	access(x);f[x].rev^=1;
}

void link(int x,int y) {
	makeroot(x);f[x].par=y;
}

void cut(int x,int y) {
	makeroot(x);access(y);f[x].par=f[y].l=0;update(y);
}

int query(int x,int y) {
	makeroot(x);access(y);
	//
}

void change(int x,int y) {
	makeroot(x);access(y);
	//
}

bool isconnect(int x,int y) {
	makeroot(x);access(y);
	while (push(y),f[y].l) y=f[y].l;
	splay(y);
	return x==y;
}

int main() {
}