ll n1,n2,n3,m,S,T,tot=1;
ll head[MAXN],now[MAXN],dis[MAXN];
struct node{
	ll v,w,nxt;
}e[MR<<1]; 
bool bfs(){
	FL(i,S,T) dis[i]=inf;
	queue<ll>q;
	q.push(S);
	dis[S]=0,now[S]=head[S];
	while(!q.empty()){
		ll u=q.front();
		q.pop();
		for(ll i=head[u];i;i=e[i].nxt){
			ll v=e[i].v;
			if(e[i].w&&dis[v]==inf){
				now[v]=head[v];
				dis[v]=dis[u]+1;
				q.push(v);
				if(v==T) return 1;
			}
		}
	}
	return 0;
}
ll dfs(ll u,ll flow){
	if(u==T) return flow;
	ll res=0;
	for(ll i=now[u];i&&flow;i=e[i].nxt){
		ll v=e[i].v;
		now[u]=i;
		if(e[i].w&&(dis[v]==dis[u]+1)){
			ll tmp=dfs(v,min(flow,e[i].w));
			if(!tmp) dis[v]=inf;
			e[i].w-=tmp;
			e[i^1].w+=tmp;
			res+=tmp,flow-=tmp;
		}
	}
	return res;
}
ll dinic(){
	ll res=0;
	while(bfs()) res+=dfs(S,inf);
	return res;
}
void add_edge(ll u,ll v,ll w){
	e[++tot].v=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void Add(ll u,ll v,ll w){
	add_edge(u,v,w);
	add_edge(v,u,0); 
}

ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	ll gcd=exgcd(b,a%b,x,y);
	ll tmp=x;
	x=y;
	y=tmp-a/b*y;
	return gcd;
}

int dfn[MAXN],low[MAXN],idx=0;
int s[MAXN],top=0;
int scc[MAXN],num=0;
bool vis[MAXN]; 
int in[MAXN],out[MAXN];
vector<int>G[MAXN];
void tarjan(int u){
	dfn[u]=low[u]=++idx;
	s[++top]=u;
	vis[u]=1;
	for(int v:G[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		scc[u]=++num;
		vis[u]=0;
		while(u!=s[top]) vis[s[top]]=0,scc[s[top--]]=num;
		top--;
	}
}

int dfn[MAXN],low[MAXN],idx=0;
int s[MAXN],top=0;
int num;
int f[30][MAXN];
int d[MAXN];
vector<int>G[MAXN],g[MAXN];
void tarjan(int u){
	dfn[u]=low[u]=++idx;
	s[++top]=u;
	for(int v:G[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			if(low[v]==dfn[u]){
				num++;
				g[num].push_back(v);
				g[v].push_back(num);
				while(v!=s[top]){
					g[num].push_back(s[top]);
					g[s[top--]].push_back(num);
				}
				top--;
				g[num].push_back(u);
				g[u].push_back(num);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
} 

struct node{
	int v,nxt;
}e[MAXN<<1];
int head[MAXN],tot=1;
int dfn[MAXN],low[MAXN],idx=0;
int s[MAXN],top=0,scc[MAXN],in[MAXN],num=0;
void add(int u,int v){
	e[++tot].v=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void tarjan(int u,int eid){
	dfn[u]=low[u]=++idx;
	s[++top]=u;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
		}
		else if(i!=(eid^1)) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		scc[u]=++num;
		while(u!=s[top]) scc[s[top--]]=num;
		top--;
	}
}

ll n,q,rt;
ll f[30][MAXN],lg[MAXN];
ll dep[MAXN],h[MAXN],son[MAXN];
ll top[MAXN];
vector<ll>G[MAXN],Up[MAXN],Down[MAXN];
void dfs1(ll u,ll fth){
	h[u]=dep[u]=dep[fth]+1;
	f[0][u]=fth;
	FL(i,1,29) f[i][u]=f[i-1][f[i-1][u]];
	for(ll v:G[u]){
		if(v==fth) continue;
		dfs1(v,u);
		h[u]=max(h[u],h[v]);
		if(h[v]>h[son[u]]) son[u]=v; 
	}
}
void dfs2(ll u,ll tp){
	top[u]=tp;
	if(u==tp){
		ll x=u;
		FL(i,0,h[u]-dep[u]) Up[u].push_back(x),x=f[0][x];
		x=u;
		FL(i,0,h[u]-dep[u]) Down[u].push_back(x),x=son[x];
	}
	if(son[u]) dfs2(son[u],tp);
	for(ll v:G[u]){
		if(v==f[0][u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
ll ask(ll x,ll k){
	if(!k) return x;
	x=f[lg[k]][x];
	k-=(1<<lg[k]);
	k-=(dep[x]-dep[top[x]]);
	x=top[x];
	return ((k>=0)?Up[x][k]:Down[x][-k]);
}