#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define szz(r) (ll)r.size()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e5+5;
vector<int>g[mxn];
int sz[mxn],id[mxn],head[mxn],pr[mxn],cu=0,lst[mxn],mode[mxn]{0};
struct node{
ll aa,ab,ba,bb;
node operator+(node b){
node rs;
if(aa==-1)return b;
if(b.aa==-1)return (rs={aa,ab,ba,bb});
rs.aa=min({aa+b.aa,aa+b.ba+1,ab+b.aa+1,ab+b.ba});
rs.ab=min({aa+b.ab,aa+b.bb+1,ab+b.ab+1,ab+b.bb});
rs.ba=min({ba+b.aa,ba+b.ba+1,bb+b.ba,bb+b.aa+1});
rs.bb=min({ba+b.ab,ba+b.bb+1,bb+b.bb,bb+b.ab+1});
return rs;
}
}t[4*mxn],sum[mxn];
void print(node x){
cout<<x.aa<<' '<<x.ab<<' '<<x.ba<<' '<<x.bb<<'\n';
}
void build(int i,int l,int r){
if(l==r){
t[i]={0,(ll)1e9,(ll)1e9,0},sum[l]={0,0,0,0};
return;
}
int m=(l+r)>>1;
build(2*i,l,m);build(2*i+1,m+1,r);
t[i]=t[2*i]+t[2*i+1];
}
void uni(int i,int l){
if(mode[l]==0){
t[i].aa=min({t[i].aa+sum[l].aa,t[i].aa+sum[l].ab,t[i].aa+sum[l].ba+1,t[i].aa+sum[l].bb+1});
t[i].bb=min({t[i].bb+sum[l].bb,t[i].bb+sum[l].ba,t[i].bb+sum[l].ab+1,t[i].bb+sum[l].aa+1});
}
if(mode[l]==1){
t[i].aa = min({t[i].aa+sum[l].aa,t[i].aa+sum[l].ab,t[i].aa+sum[l].ba+1,t[i].aa+sum[l].bb+1});
}
if(mode[l]==2){
t[i].bb = min({t[i].bb+sum[l].bb,t[i].bb+sum[l].ba,t[i].bb+sum[l].ab+1,t[i].bb+sum[l].aa+1});
}
}
void update(int i,int l,int r,int idx,int v){
if(r<idx||l>idx)return;
if(l==r){
if(v==1){
t[i]={0,(ll)1e9,(ll)1e9,(ll)1e9};
uni(i,l);
return;
}
else if(v==2){
t[i]={(ll)1e9,(ll)1e9,(ll)1e9,0};
uni(i,l);
return;
}
else if(v==0){
t[i]={0,(ll)1e9,(ll)1e9,0};
uni(i,l);
return;
}
else {
if(mode[l]==0)t[i]={0,(ll)1e9,(ll)1e9,0};
else if(mode[l]==1)t[i]={0,(ll)1e9,(ll)1e9,(ll)1e9};
else if(mode[l]==2)t[i]={(ll)1e9,(ll)1e9,(ll)1e9,0};
uni(i,l);
return;
}
}int m=(l+r)>>1;
update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
t[i]=t[2*i]+t[2*i+1];
}
node qr(int i,int l,int r,int tl,int tr){
if(r<tl||l>tr)return {-1,-1,-1,-1};
if(r<=tr&&l>=tl){
return t[i];
}
int m=(l+r)>>1;
return qr(2*i,l,m,tl,tr)+qr(2*i+1,m+1,r,tl,tr);
}
void dfssz(int u,int p){
sz[u]=1;pr[u]=p;
for(auto v:g[u]){
if(v==p)continue;
dfssz(v,u);sz[u]+=sz[v];
}
}
void hld(int u,int p,int tp){
head[u]=tp;id[u]=++cu;lst[tp]=id[u];
int hv=-1;
for(auto v:g[u]){
if(v==p)continue;
if(hv==-1||sz[hv]<sz[v])hv=v;
}if(hv==-1)return;
hld(hv,u,tp);
for(auto v:g[u]){
if(v==hv||v==p)continue;
hld(v,u,v);
}
}int n;
void initialize(int N, std::vector<int> A, std::vector<int> B){
n=N;
for(int i=0;i<N-1;i++){
g[A[i]].pb(B[i]);g[B[i]].pb(A[i]);
}dfssz(1,-1);hld(1,1,1);
build(1,1,n);
}
int cat(int v){
int x=v;
while(x!=-1){
node sp=qr(1,1,n,id[head[x]],lst[head[x]]);
if(pr[head[x]]!=-1){
int idx=id[pr[head[x]]];
sum[idx]={sum[idx].aa-min(sp.aa,sp.ab),sum[idx].ab-min(sp.ab,sp.aa),sum[idx].ba-min(sp.ba,sp.bb),sum[idx].bb-min(sp.bb,sp.ba)};
}if(x==v)mode[id[x]]=1,update(1,1,n,id[x],1);
else update(1,1,n,id[x],4);
sp=qr(1,1,n,id[head[x]],lst[head[x]]);
if(pr[head[x]]!=-1){
int idx=id[pr[head[x]]];
sum[idx]={sum[idx].aa+min(sp.aa,sp.ab),sum[idx].ab+min(sp.ab,sp.aa),sum[idx].ba+min(sp.ba,sp.bb),sum[idx].bb+min(sp.bb,sp.ba)};
}x=pr[head[x]];
}
node rs=qr(1,1,n,id[1],lst[1]);
return min({rs.aa,rs.ab,rs.ba,rs.bb});
}
int dog(int v) {
int x=v;
while(x!=-1){
node sp=qr(1,1,n,id[head[x]],lst[head[x]]);
if(pr[head[x]]!=-1){
int idx=id[pr[head[x]]];
sum[idx]={sum[idx].aa-sp.aa,sum[idx].ab-sp.ab,sum[idx].ba-sp.ba,sum[idx].bb-sp.bb};
}if(x==v)mode[id[x]]=2,update(1,1,n,id[x],2);
else update(1,1,n,id[x],4);
sp=qr(1,1,n,id[head[x]],lst[head[x]]);
if(pr[head[x]]!=-1){
int idx=id[pr[head[x]]];
sum[idx]={sum[idx].aa+sp.aa,sum[idx].ab+sp.ab,sum[idx].ba+sp.ba,sum[idx].bb+sp.bb};
}x=pr[head[x]];
}
node rs=qr(1,1,n,id[1],lst[1]);
return min({rs.aa,rs.ab,rs.ba,rs.bb});
}
int neighbor(int v) {
int x=v;
while(x!=-1){
node sp=qr(1,1,n,id[head[x]],lst[head[x]]);
if(pr[head[x]]!=-1){
int idx=id[pr[head[x]]];
sum[idx]={sum[idx].aa-sp.aa,sum[idx].ab-sp.ab,sum[idx].ba-sp.ba,sum[idx].bb-sp.bb};
}if(x==v)mode[id[x]]=0,update(1,1,n,id[x],0);
else update(1,1,n,id[x],4);
sp=qr(1,1,n,id[head[x]],lst[head[x]]);
if(pr[head[x]]!=-1){
int idx=id[pr[head[x]]];
sum[idx]={sum[idx].aa+sp.aa,sum[idx].ab+sp.ab,sum[idx].ba+sp.ba,sum[idx].bb+sp.bb};
}x=pr[head[x]];
}
node rs=qr(1,1,n,id[1],lst[1]);
return min({rs.aa,rs.ab,rs.ba,rs.bb});
}
/*int main(){
initialize(10,{1,2,3,4,5,3,7,8,9},{2,3,4,5,6,7,8,9,10});
cout<<cat(6)<<'\n';
cout<<dog(5)<<'\n';
cout<<dog(4)<<'\n';
cout<<cat(3)<<'\n';
//print(sum[id[3]]);
}*/
