#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ll K=350;
const ld pi=acos(-1);
const long long INF=(1LL<<28);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll sz[N],p[N],vid[N],ip[N],top[N],tseg[N],color[N];
vector<ll> v[N],lis;
queue<ll> q;
ll u[N],a[N],b[N];
struct Segment_Tree{
vector<ll> u;
vector<ll> seg[2][2];
Segment_Tree(vector<ll> tmp):u(tmp){
REP(i,2)REP(j,2)seg[i][j].resize(4*(SZ(tmp)+1));
REP(i,SZ(u))ins(1,0,SZ(u),i);
};
ll A(){return min(seg[0][0][1],seg[0][1][1]);}
ll B(){return min(seg[1][0][1],seg[1][1][1]);}
void ins(ll id,ll l,ll r,ll to){
if(l==r-1){
if(color[u[l]]==0){
seg[0][0][id]=a[u[l]];seg[0][1][id]=seg[1][0][id]=INF;seg[1][1][id]=b[u[l]];
}else{
REP(i,2)REP(j,2)seg[i][j][id]=INF;
seg[color[u[l]]-1][color[u[l]]-1][id]=(color[u[l]]==1?a[u[l]]:b[u[l]]);
}
return ;
}
ll mid=(l+r)>>1;
if(to<mid){
ins(id*2,l,mid,to);
}else{
ins(id*2+1,mid,r,to);
}
REP(i,2)REP(j,2){
seg[i][j][id]=INF;
REP(ii,2)REP(jj,2)seg[i][j][id]=min(seg[i][j][id],seg[i][ii][id*2]+seg[jj][j][id*2+1]+(ii==jj?0:1));
}
}
void upd(ll to){
ins(1,0,SZ(u),to);
}
};
vector<Segment_Tree> vseg;
/*void DFS(ll nd,ll pa){
dp[nd][1]=dp[nd][2]=0;
for(auto i:v[nd]){
if(i==pa)continue;
DFS(i,nd);
dp[nd][1]+=min(dp[i][1],dp[i][2]+1);
dp[nd][2]+=min(dp[i][2],dp[i][1]+1);
}
if(col[nd]){dp[nd][3-col[nd]]=INF;}
}*/
void build(){
function<void(int,int)> predfs=[&](int nd,int pa){
sz[nd]=1;p[nd]=pa;vid[nd]=0;
for(int i:v[nd]){
if(i==pa)continue;
predfs(i,nd);
sz[nd]+=sz[i];
if(sz[vid[nd]]<sz[i])vid[nd]=i;
}
};
predfs(1,0);
q.push(1);
while(SZ(q)){
ll x=q.front();q.pop();
lis.clear();
top[x]=x;lis.pb(x);
while(vid[x]){
for(int i:v[x])if(i!=p[x]&&i!=vid[x])q.push(i);
lis.pb(vid[x]);top[vid[x]]=top[x];
x=vid[x];
}
vseg.pb(Segment_Tree(lis));
REP(i,SZ(lis))ip[lis[i]]=i,tseg[lis[i]]=SZ(vseg)-1;
}
}
void update(ll nd){
while(nd){
a[p[top[nd]]]-=min(vseg[tseg[nd]].A(),vseg[tseg[nd]].B()+1);
b[p[top[nd]]]-=min(vseg[tseg[nd]].A()+1,vseg[tseg[nd]].B());
vseg[tseg[nd]].upd(ip[nd]);
a[p[top[nd]]]+=min(vseg[tseg[nd]].A(),vseg[tseg[nd]].B()+1);
b[p[top[nd]]]+=min(vseg[tseg[nd]].A()+1,vseg[tseg[nd]].B());
nd=p[top[nd]];
}
}
void initialize(ll n,vector<ll> ea,vector<ll> eb){
REP(i,n-1)v[ea[i]].pb(eb[i]),v[eb[i]].pb(ea[i]);
build();
}
ll cat(ll id){
color[id]=1;
update(id);
return min(vseg[0].A(),vseg[0].B());
}
ll dog(ll id){
color[id]=2;
update(id);
return min(vseg[0].A(),vseg[0].B());
}
ll neighbor(ll id){
color[id]=0;
update(id);
return min(vseg[0].A(),vseg[0].B());
}
/*
int main(){
ll n;
cin>>n;
vector<ll> ea(n-1),eb(n-1);
REP(i,n-1)cin>>ea[i]>>eb[i];
initialize(n,ea,eb);
return 0;
}*/
