#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
int sz[100009],mx[100009],h[100009],ver[200009],nxt[200009],tot,ff[100009],tp[100009],dfn[100009],ed[100009],n;
struct nd{
	int x[2];
}g[100009];
struct node{
	int x[4];
	node operator +(const node &aa)const{
		node cc;
		cc.x[0]=min(min(x[0]+aa.x[2],x[1]+aa.x[0])+1,min(x[0]+aa.x[0],x[1]+aa.x[2]));
		cc.x[1]=min(min(x[0]+aa.x[3],x[1]+aa.x[1])+1,min(x[0]+aa.x[1],x[1]+aa.x[3]));
		cc.x[2]=min(min(x[2]+aa.x[2],x[3]+aa.x[0])+1,min(x[2]+aa.x[0],x[3]+aa.x[2]));
		cc.x[3]=min(min(x[2]+aa.x[3],x[3]+aa.x[1])+1,min(x[2]+aa.x[1],x[3]+aa.x[3]));
		cc.x[0]=min(cc.x[0],0x3f3f3f3f);
		cc.x[1]=min(cc.x[1],0x3f3f3f3f);
		cc.x[2]=min(cc.x[2],0x3f3f3f3f);
		cc.x[3]=min(cc.x[3],0x3f3f3f3f);
		return cc;
	}
	node operator +(const nd &aa)const{
		node cc;
		cc.x[1]=cc.x[2]=0x3f3f3f3f;
		cc.x[0]=x[0]+min(aa.x[1]+1,aa.x[0]);
		cc.x[3]=x[3]+min(aa.x[1],aa.x[0]+1);
		return cc;
	}
}f[100009],d[100009],val[400009];
void add(nd &cc,node aa){
	cc.x[0]+=min(min(aa.x[2],aa.x[3])+1,min(aa.x[0],aa.x[1]));
	cc.x[1]+=min(min(aa.x[2],aa.x[3]),min(aa.x[0],aa.x[1])+1);
}
void del(nd &cc,node aa){
	cc.x[0]-=min(min(aa.x[2],aa.x[3])+1,min(aa.x[0],aa.x[1]));
	cc.x[1]-=min(min(aa.x[2],aa.x[3]),min(aa.x[0],aa.x[1])+1);
}
void dfs1(int x,int fa){
	sz[x]=1;
	for(int i=h[x];i;i=nxt[i]){
		if(ver[i]!=fa){
			dfs1(ver[i],x);
			sz[x]+=sz[ver[i]];
			if(sz[ver[i]]>sz[mx[x]])mx[x]=ver[i];
		}
	}
}
void dfs2(int x,int fa,int tt){
	tp[x]=tt;
	ed[tt]=x;
	ff[x]=fa;
	dfn[x]=++tot;
	if(mx[x])dfs2(mx[x],x,tt);
	for(int i=h[x];i;i=nxt[i]){
		if(ver[i]!=fa&&ver[i]!=mx[x]){
			dfs2(ver[i],x,ver[i]);
		}
	}
}
void build(int rt,int l,int r){
	if(l==r){
		val[rt]=f[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	val[rt]=val[rt<<1]+val[rt<<1|1];
}
void update(int rt,int l,int r,int ll,node rr){
	if(ll<l)return;
	if(l==r){
		val[rt]=rr;
		return;
	}
	int mid=(l+r)>>1;
	if(ll<=mid)update(rt<<1,l,mid,ll,rr);
	else update(rt<<1|1,mid+1,r,ll,rr);
	val[rt]=val[rt<<1]+val[rt<<1|1];
}
node query(int rt,int l,int r,int ll,int rr){
	if(l>rr||r<ll){
		node rtn;
		rtn.x[0]=rtn.x[3]=0;
		rtn.x[1]=rtn.x[2]=1;
		return rtn;
	}
	if(l>=ll&&r<=rr){
		return val[rt];
	}
	int mid=(l+r)>>1;
	return query(rt<<1,l,mid,ll,rr)+query(rt<<1|1,mid+1,r,ll,rr);
}
void initialize(int N,vector<int> A,vector<int> B) {
	n=N;
	for(int i=0;i<n-1;i++){
		tot++;
		nxt[tot]=h[A[i]];
		ver[tot]=B[i];
		h[A[i]]=tot;
		tot++;
		nxt[tot]=h[B[i]];
		ver[tot]=A[i];
		h[B[i]]=tot;
	}
	for(int i=1;i<=n;i++){
		f[i].x[0]=f[i].x[3]=0;
		f[i].x[1]=f[i].x[2]=0x3f3f3f3f;
	}
	dfs1(1,0);
	tot=0;
	dfs2(1,0,1);
	build(1,1,n);
}

int cat(int v){
	f[v].x[0]=0;
	f[v].x[1]=f[v].x[2]=f[v].x[3]=0x3f3f3f3f;
	update(1,1,n,dfn[v],f[v]+g[v]); 
	while(v){
		int u=tp[v];
		int w=ed[u];
		del(g[ff[u]],d[u]);
		d[u]=query(1,1,n,dfn[u],dfn[w]);
		add(g[ff[u]],d[u]);
		update(1,1,n,dfn[ff[u]],f[ff[u]]+g[ff[u]]);
		v=ff[u];
	}
	return min(min(d[1].x[0],d[1].x[1]),min(d[1].x[2],d[1].x[3]));
}

int dog(int v) {
	f[v].x[0]=f[v].x[1]=f[v].x[2]=0x3f3f3f3f;
	f[v].x[3]=0;
	update(1,1,n,dfn[v],f[v]+g[v]); 
	while(v){
		int u=tp[v];
		int w=ed[u];
		del(g[ff[u]],d[u]);
		d[u]=query(1,1,n,dfn[u],dfn[w]);
		add(g[ff[u]],d[u]);
		update(1,1,n,dfn[ff[u]],f[ff[u]]+g[ff[u]]);
		v=ff[u];
	}
	return min(min(d[1].x[0],d[1].x[1]),min(d[1].x[2],d[1].x[3]));
}

int neighbor(int v) {
	f[v].x[0]=f[v].x[3]=0;
	f[v].x[1]=f[v].x[2]=0x3f3f3f3f;
	update(1,1,n,dfn[v],f[v]+g[v]); 
	while(v){
		int u=tp[v];
		int w=ed[u];
		del(g[ff[u]],d[u]);
		d[u]=query(1,1,n,dfn[u],dfn[w]);
		add(g[ff[u]],d[u]);
		update(1,1,n,dfn[ff[u]],f[ff[u]]+g[ff[u]]);
		v=ff[u];
	}
	return min(min(d[1].x[0],d[1].x[1]),min(d[1].x[2],d[1].x[3]));
}