#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
vector<int> adj[200001];
int n;
int val[200001];
int sz[200001];
int P[200001];
int arr[200001];
int root[200001];
int down[200001];
void co(int i,int pr){
sz[i] = 1;
for(auto j:adj[i]){
if(j==pr)continue;
co(j,i);
sz[i]+=sz[j];
}
}
int no = 1;
void dfs(int i,int pr,int ro){
val[i] = no++;
root[i] = ro;
down[ro] = i;
P[i] = pr;
int ma = -1 , su = 0;
for(auto j:adj[i]){
if(j==pr)continue;
if(ma<sz[j]){
ma = sz[j];
su = j;
}
}
if(ma!=-1)dfs(su,i,ro);
for(auto j:adj[i]){
if(j==pr||j==su)continue;
dfs(j,i,j);
}
}
struct node{
int dp[2][2];
node(){
for(int i = 0;i<2;i++){
for(int j = 0;j<2;j++){
dp[i][j] = 1e5;
}
}
}
}seg[400001];
node combine(node a,node b){
node ans;
for(int i = 0;i<2;i++){
for(int j = 0;j<2;j++){
for(int k = 0;k<2;k++){
for(int l = 0;l<2;l++){
ans.dp[i][j] = min(ans.dp[i][j],a.dp[i][k]+b.dp[l][j]+(k != l));
}
}
}
}
return ans;
}
void build(int l,int r,int p){
//cout<<l<<" "<<r<<" "<<p<<endl;
if(l==r){
seg[p].dp[0][0] = 0;
seg[p].dp[1][1] = 0;
seg[p].dp[0][1] = 1e5;
seg[p].dp[1][0] = 1e5;
return ;
}
int md = (l+r)/2;
build(l,md,p*2);
build(md+1,r,p*2+1);
seg[p] = combine(seg[p*2],seg[p*2+1]);
}
void update(int l,int r,int p,int idx,pair<int,int> val){
if(l==r){
seg[p].dp[0][0] = val.first;
seg[p].dp[1][1] = val.second;
seg[p].dp[0][1] = 1e5;
seg[p].dp[1][0] = 1e5;
return ;
}
int md = (l+r)/2;
if(idx<=md)update(l,md,p*2,idx,val);
else update(md+1,r,p*2+1,idx,val);
seg[p] = combine(seg[p*2],seg[p*2+1]);
}
node query(int l,int r,int p,int lq,int rq){
//cout<<p<<" "<<l<<" "<<r<<endl;
if(l>=lq&&r<=rq)return seg[p];
int md = (l+r)/2;
if(lq<=md&&rq>=md+1){
return combine(query(l,md,p*2,lq,rq),query(md+1,r,p*2+1,lq,rq));
}
if(lq<=md){
return query(l,md,p*2,lq,rq);
}else return query(md+1,r,p*2+1,lq,rq);
}
int coll[100001];
int sum[100001][2];
int prv[100001][2];
node upd(int x){
if(coll[x]==0)update(1, n,1, val[x], {sum[x][0], 1e5});
if(coll[x]==1)update(1, n,1, val[x], {1e5, sum[x][1]});
if(coll[x]==2)update(1, n,1, val[x], {sum[x][0], sum[x][1]});
x = root[x];
//cout<<x<<" "<<val[x]<<" "<<val[down[x]]<<"rng"<<endl;
node ans = query(1,n,1,val[x],val[down[x]]);
if(x==1){
return ans;
}
for(int i = 0;i<2;i++){
sum[P[x]][i] -= prv[x][i];
int best = 1e5;
for(int j = 0;j<2;j++){
best = min(best,ans.dp[i][j]);
best = min(best,ans.dp[i ^ 1][j] + 1);
}
prv[x][i] = best;
sum[P[x]][i]+=prv[x][i];
}
return upd(P[x]);
}
void initialize(int N,vector<int>A,vector<int>B){
n = N;
coll[0] = 2;coll[N] = 2;
for(int i = 0;i<N-1;i++){
coll[i+1] = 2;
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
//cout<<"ff"<<endl;
co(1,1);
//cout<<"ff"<<endl;
dfs(1,1,1);
//cout<<"ff"<<endl;
build(1,n,1);
//cout<<"ff"<<endl;
}
int cat(int v){
coll[v] = 0;
//cout<<"ff"<<endl;
node ans = upd(v);
int best = 1e5;
for(int i = 0;i<2;i++){
for(int j = 0;j<2;j++){
best = min(best,ans.dp[i][j]);
}
}
return best;
}int dog(int v){
coll[v] = 1;
node ans = upd(v);
int best = 1e5;
for(int i = 0;i<2;i++){
for(int j = 0;j<2;j++){
best = min(best,ans.dp[i][j]);
}
}
return best;
}int neighbor(int v){
coll[v] = 2;
node ans = upd(v);
int best = 1e5;
for(int i = 0;i<2;i++){
for(int j = 0;j<2;j++){
best = min(best,ans.dp[i][j]);
}
}
return best;
}/*
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int N = 5;
vector<int> A = {1,2,2,4};
vector<int> B = {2,3,4,5};
initialize(N,A,B);
cout<<"hh"<<endl;
cout<<cat(3)<<"jjjjjjjjjjjj"<<endl;
cout<<dog(5)<<"jjjjjjjjjjjj"<<endl;
cout<<dog(1)<<"jjjjjjjjjjjj"<<endl;
cout<<cat(2)<<"jjjjjjjjjjjj"<<endl;
cout<<neighbor(2)<<"jjjjjjjjjjjj"<<endl;
}*/
