#include <iostream>
#include <vector>
#include <algorithm>
#define fi first
#define se second
using namespace std;
using ll = long long;
ll inf = 1'000'000'000;
int n;
int idx;
vector<int> G,nxt,top,A;
vector<int> sz,lvl,hv_son,pos,head,T,lg;
struct Nod
{
int mat[2][2]={0};
Nod()
{
mat[0][0]=mat[1][1]=0;
mat[0][1]=mat[1][0]=inf;
}
};
Nod combine(Nod a,Nod b)
{
Nod ans;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
ans.mat[i][j]=inf;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int x=0;x<2;x++)
for(int y=0;y<2;y++)
ans.mat[i][j]=min(ans.mat[i][j],a.mat[i][x]+b.mat[y][j]+
( (x==y) ? 0 : 1));
return ans;
}
struct segtree
{
vector<Nod> aint;
void init(int _n)
{
aint=vector<Nod>(4*_n+5);
}
void update(int node,int st,int dr,int x,int cat,int dog)
{
if(st==dr)
{
aint[node].mat[0][0]+=cat;
aint[node].mat[1][1]+=dog;
return;
}
int mij=(st+dr)>>1;
if(x<=mij)
update(2*node,st,mij,x,cat,dog);
else
update(2*node+1,mij+1,dr,x,cat,dog);
aint[node]=combine(aint[2*node],aint[2*node+1]);
}
pair<int,int> get()
{
Nod ans=aint[1];
int cat=min({ans.mat[0][0],ans.mat[0][1],ans.mat[1][0]+1,ans.mat[1][1]+1});
int dog=min({ans.mat[1][0],ans.mat[1][1],ans.mat[0][0]+1,ans.mat[0][1]+1});
return {cat,dog};
}
};
vector<segtree> st;
void add_edge(int x,int y)
{
idx++;
G[idx]=y;
nxt[idx]=top[x];
top[x]=idx;
}
void dfs(int x,int tata)
{
lvl[x]=lvl[tata]+1;
sz[x]=1;
T[x]=tata;
int sz_max=0;
for(int i=top[x];i;i=nxt[i])
{
int y=G[i];
if(y==tata)
continue;
sz[x]+=sz[y];
dfs(y,x);
if(sz[y]>sz_max)
{
sz_max=sz[y];
hv_son[x]=y;
}
}
}
void decompose(int x,int hd)
{
head[x]=hd;
pos[x]=++lg[hd];
if(hv_son[x])
decompose(hv_son[x],hd);
for(int i=top[x];i;i=nxt[i])
{
int y=G[i];
if(y==T[x] || y==hv_son[x])
continue;
decompose(y,y);
}
}
void initialize(int _n,vector<int> a,vector<int> b)
{
n=_n;
G=nxt=vector<int>(2*n+1);
top=A=sz=lvl=hv_son=pos=head=T=lg=vector<int>(n+1);
for(int i=1;i<=n-1;i++)
{
add_edge(a[i-1],b[i-1]);
add_edge(b[i-1],a[i-1]);
}
dfs(1,0);
decompose(1,1);
st=vector<segtree>(n+1);
for(int i=1;i<=n;i++)
if(head[i]==i)
st[i].init(lg[i]+5);
}
void solve(int x,int cat,int dog)
{
while(head[x])
{
auto [c0,d0]=st[head[x]].get();
st[head[x]].update(1,1,lg[head[x]],pos[x],cat,dog);
auto [c1,d1]=st[head[x]].get();
cat=c1-c0;
dog=d1-d0;
x=T[head[x]];
}
}
int get_ans()
{
Nod ans=st[1].aint[1];
int sol=inf;
/*for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
sol=min(sol,ans.mat[i][j]);*/
sol=min(ans.mat[0][0],ans.mat[1][1]);
return sol;
}
int cat(int x)
{
A[x]=0;
solve(x,0,inf);
return get_ans();
}
int dog(int x)
{
A[x]=1;
solve(x,inf,0);
return get_ans();
}
int neighbor(int x)
{
if(A[x]==0)
solve(x,0,-inf);
if(A[x]==1)
solve(x,-inf,0);
return get_ans();
}
