#include <bits/stdc++.h>
#define pii pair<int,int>
#define iii pair<int,pii>
#define fi first
#define se second
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define TEXT "a"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int inf = 1e9 + 7;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 1e5 + 5;
int n;
vector<int> a[N];
int f[N], g[N];
int preF[N], preG[N];
int type[N];
int pa[N];
void dfs(int u,int p){
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i];
if (v == p) continue;
pa[v] = u;
dfs(v,u);
}
}
void brute(int u,int p){
if (type[u] == 0) f[u] = g[u] = 0;
if (type[u] == 1) f[u] = 0, g[u] = inf;
if (type[u] == 2) f[u] = inf, g[u] = 0;
for(int v : a[u]){
if (v == p) continue;
brute(v,u);
if (f[u] != inf) f[u] += min(f[v], g[v] + 1);
if (g[u] != inf) g[u] += min(f[v] + 1, g[v]);
}
}
void initialize(int N,vector<int> u, vector<int> v){
n = N;
for (int i = 0; i < n - 1; i++){
a[u[i]].push_back(v[i]);
a[v[i]].push_back(u[i]);
}
dfs(1,-1);
}
int cat(int u){
type[u] = 1;
// brute(1,-1);
g[u] = inf;
while(u != 1){
int p = pa[u];
///f[p] += min(f[u], g[u] + 1)
if (f[p] != inf){
if (preF[u] <= preG[u] + 1) f[p] += -preF[u] + min(f[u], g[u] + 1);
if (preG[u] + 1 <= preF[u]) f[p] += -(preG[u] + 1) + min(f[u], g[u] + 1);
}
if (g[p] != inf){
if (preG[u] <= preF[u] + 1) g[p] += -preG[u] + min(f[u] + 1, g[u]);
if (preF[u] + 1 <= preG[u]) g[p] += -(preF[u] + 1) + min(f[u] + 1, g[u]);
}
preF[u] = f[u];
preG[u] = g[u];
u = p;
}
return min(f[1], g[1]);
}
int dog(int u){
type[u] = 2;
f[u] = inf;
while(u != 1){
int p = pa[u];
///f[p] += min(f[u], g[u] + 1)
if (f[p] != inf){
if (preF[u] <= preG[u] + 1) f[p] += -preF[u] + min(f[u], g[u] + 1);
if (preG[u] + 1 <= preF[u]) f[p] += -(preG[u] + 1) + min(f[u], g[u] + 1);
}
if (g[p] != inf){
if (preG[u] <= preF[u] + 1) g[p] += -preG[u] + min(f[u] + 1, g[u]);
if (preF[u] + 1 <= preG[u]) g[p] += -(preF[u] + 1) + min(f[u] + 1, g[u]);
}
preF[u] = f[u];
preG[u] = g[u];
u = p;
}
// brute(1,-1);
return min(f[1], g[1]);
}
int neighbor(int u){
type[u] = 0;
f[u] = g[u] = 0;
for (int v : a[u]){
if (v == pa[u]) continue;
f[u] += min(f[v], g[v] + 1);
g[u] += min(g[v], f[v] + 1);
}
while(u != 1){
int p = pa[u];
///f[p] += min(f[u], g[u] + 1)
if (f[p] != inf){
if (preF[u] <= preG[u] + 1) f[p] += -preF[u] + min(f[u], g[u] + 1);
if (preG[u] + 1 <= preF[u]) f[p] += -(preG[u] + 1) + min(f[u], g[u] + 1);
}
if (g[p] != inf){
if (preG[u] <= preF[u] + 1) g[p] += -preG[u] + min(f[u] + 1, g[u]);
if (preF[u] + 1 <= preG[u]) g[p] += -(preF[u] + 1) + min(f[u] + 1, g[u]);
}
preF[u] = f[u];
preG[u] = g[u];
u = p;
}
// brute(1,-1);
return min(f[1], g[1]);
}
//int main(){
// cin.tie(0) -> sync_with_stdio(0);
// if (fopen(TEXT".inp","r")){
// freopen(TEXT".inp","r",stdin);
// freopen(TEXT".out","w",stdout);
// }
// int N = 5;
// vector<int> A = {1,2,2,4};
// vector<int> B = {2,3,4,5};
// initialize(N,A,B);
// vector<pii> order = {pii(1,3),pii(2,5),pii(1,2),pii(2,1),pii(3,2)};
// for (auto [type, u] : order){
// if (type == 1) cout << cat(u) << "\n";
// if (type == 2) cout << dog(u) << "\n";
// if (type == 3) cout << neighbor(u) << "\n";
// }
// return 0;
//}
