#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int inf = 1e9;
vector<int> a[N];
int pa[N], sz[N], heavy[N];
int head[N], tin[N], curTime;
int SC[N], SD[N];
int id[N], chainSz[N], chainCnt;
int n;
struct node{
int val[2][2];
node(){
val[0][0] = val[0][1] = val[1][0] = val[1][1] = inf;
}
};
node combine(node& a,node& b){
node n;
for (int x = 0; x < 2; x++){
for (int y = 0; y < 2; y++){
for (int i = 0; i < 2; i++){
for (int j = 0; j < 2; j++){
n.val[x][y] = min(n.val[x][y], a.val[x][i] + b.val[j][y] + (i != j));
}
}
}
}
return n;
}
class IT{
private:
vector<node> t;
int n;
public:
void init(int m){
n = m;
t.resize(n * 4);
}
void build(int id,int l,int r){
if (l == r){
t[id].val[0][0] = 0;
t[id].val[1][1] = 0;
t[id].val[0][1] = t[id].val[1][0] = inf;
return;
}
int mid = (l + r) / 2;
build(id * 2,l,mid);
build(id * 2 + 1,mid + 1,r);
t[id] = combine(t[id * 2],t[id * 2 + 1]);
}
void build(){
build(1,1,n);
}
void update(int id,int l,int r,int i,int cat,int dog){
if (l > i || r < i) return;
if (l == r){
t[id].val[0][0] = cat;
t[id].val[1][1] = dog;
t[id].val[0][1] = t[id].val[1][0] = inf;
return;
}
int mid = (l + r) / 2;
update(id * 2,l,mid,i,cat,dog);
update(id * 2 + 1,mid + 1,r,i,cat,dog);
t[id] = combine(t[id * 2],t[id * 2 + 1]);
}
void update(int i,int cat,int dog){
update(1,1,n,i,cat,dog);
}
node getNode(){
return t[1];
}
};
IT t[N];
void dfs(int u,int p){
sz[u] = 1;
for (int v : a[u]){
if (v == p) continue;
pa[v] = u;
dfs(v,u);
if (sz[v] > sz[heavy[u]]) heavy[u] = v;
sz[u] += sz[v];
}
}
void hld(int u,int p){
if (head[u] == 0){
head[u] = u;
id[u] = ++chainCnt;
}
chainSz[id[u]]++;
tin[u] = ++curTime;
int nxt = heavy[u];
if (nxt == 0) return;
head[nxt] = head[u];
id[nxt] = chainCnt;
hld(nxt,u);
for (int v : a[u]){
if (v == p || v == nxt) continue;
hld(v,u);
}
}
void initialize(int _N, vector<int> _A, vector<int> _B){
n = _N;
for (int i = 0; i < n - 1; i++){
int u = _A[i];
int v = _B[i];
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1,-1);
hld(1,-1);
// for (int i = 1; i <= n; i++){
// cout << i << " " << id[i] << "\n";
// }
for (int i = 1; i <= chainCnt; i++){
t[i].init(chainSz[i]);
t[i].build();
}
}
void update(int u,int cat,int dog){
while(u != 0){
node f = t[id[u]].getNode();
int preSC = min({f.val[0][0],f.val[0][1],f.val[1][0] + 1,f.val[1][1] + 1});
int preSD = min({f.val[0][0] + 1,f.val[0][1] + 1,f.val[1][0],f.val[1][1]});
SC[pa[head[u]]] -= preSC;
SD[pa[head[u]]] -= preSD;
t[id[u]].update(tin[u] - tin[head[u]] + 1,cat,dog);
// cout << tin[u] - tin[head[u]] + 1 << " " << cat << " " << dog << '\n';
node g = t[id[u]].getNode();
// cout << "g: " << g.val[0][0] << " " << g.val[1][1] << " " << g.val[0][1] << " " << g.val[1][0] << '\n';
SC[pa[head[u]]] += min({g.val[0][0],g.val[0][1],g.val[1][0] + 1,g.val[1][1] + 1});
SD[pa[head[u]]] += min({g.val[0][0] + 1,g.val[0][1] + 1,g.val[1][0],g.val[1][1]});
// cout << SC[pa[head[u]]] << " " << SD[pa[head[u]]] << "\n";
u = pa[head[u]];
cat = SC[u];
dog = SD[u];
}
}
int cat(int u){
update(u,SC[u],inf);
node f = t[id[1]].getNode();
return min({f.val[0][0],f.val[0][1],f.val[1][0],f.val[1][1]});
}
int dog(int u){
update(u,inf,SD[u]);
node f = t[id[1]].getNode();
return min({f.val[0][0],f.val[0][1],f.val[1][0],f.val[1][1]});
}
int neighbor(int u){
update(u,SC[u],SD[u]);
node f = t[id[1]].getNode();
return min({f.val[0][0],f.val[0][1],f.val[1][0],f.val[1][1]});
}
//
//int main(){
// int _N = 5;
// vector<int> _A = {1,2,2,4};
// vector<int> _B = {2,3,4,5};
// initialize(_N, _A, _B);
// cout << cat(3) << "\n";
// cout << dog(5) << "\n";
// cout << cat(2) << "\n";
// cout << dog(1) << "\n";
// cout << neighbor(2) << "\n";
//}
