#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 1e5 + 7, inf = 1e6;
int n, par[N], head[N], chain[N], pos[N], sz[N], st[N];
vector <int> edge[N];
struct node{
int dp[2][2];
node(){
dp[0][0] = dp[1][1] = 0;
dp[0][1] = dp[1][0] = inf;
}
};
node merge(node a, node b){
node ret;
for(int i = 0; i <= 1; i++){
for(int j = 0; j <= 1; j++){
ret.dp[i][j] = inf;
for(int k = 0; k <= 1; k++){
for(int l = 0; l <= 1; l++){
ret.dp[i][j] = min(ret.dp[i][j], a.dp[i][k] + b.dp[l][j] + (k ^ l));
}
}
}
}
return ret;
}
struct segtree{
vector <node> it;
int sz;
void init(int k, int l, int r){
if(l == r) return;
int mid = (l + r) >> 1;
init(k << 1, l, mid);
init(k << 1 | 1, mid + 1, r);
it[k] = merge(it[k << 1], it[k << 1 | 1]);
}
void init(int pos){
sz = pos;
it.resize(4 * sz + 5);
init(1, 1, sz);
}
void update(int k, int l, int r, int pos, int v0, int v1){
if(l > pos || r < pos) return;
if(l == r){
it[k].dp[0][0] += v0;
it[k].dp[1][1] += v1;
return;
}
int mid = (l + r) >> 1;
update(k << 1, l, mid, pos, v0, v1);
update(k << 1 | 1, mid + 1, r, pos, v0, v1);
it[k] = merge(it[k << 1], it[k << 1 | 1]);
}
void update(int pos, int v0, int v1){
update(1, 1, sz, pos, v0, v1);
}
pair <int, int> get(){
int f1 = min(it[1].dp[0][0], it[1].dp[0][1]);
int f2 = min(it[1].dp[1][0], it[1].dp[1][1]);
return mp(min(f1, f2 + 1), min(f1 + 1, f2));
}
} tree[N];
void dfs(int u, int p){
sz[u] = 1;
for(int v : edge[u]){
if(v == p) continue;
par[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
}
void hld(int u, int p){
int nxt = -1;
for(int v : edge[u]){
if(v == p) continue;
if(nxt < 0 || sz[nxt] < sz[v]){
nxt = v;
}
}
if(nxt < 0){
tree[chain[u]].init(pos[u]);
return;
}
chain[nxt] = chain[u];
pos[nxt] = pos[u] + 1;
hld(nxt, u);
for(int v : edge[u]){
if(v == p || v == nxt) continue;
chain[v] = v;
head[v] = v;
pos[v] = 1;
hld(v, u);
}
}
void initialize(int p, vector <int> A, vector <int> B){
n = p;
for(int i = 0; i < n - 1; i++){
edge[A[i]].pb(B[i]);
edge[B[i]].pb(A[i]);
}
dfs(1, 1);
head[1] = 1, chain[1] = 1, pos[1] = 1;
hld(1, 1);
}
void solve(int u, int v0, int v1){
while(u){
int cur = chain[u];
//cout << cur << endl;
int pv0, pv1;
pair <int, int> now = tree[cur].get();
pv0 = now.fi, pv1 = now.se;
tree[cur].update(pos[u], v0, v1);
now = tree[cur].get();
v0 = now.fi - pv0, v1 = now.se - pv1;
u = head[cur];
u = par[u];
}
}
int getans(){
return min(min(tree[1].it[1].dp[0][0], tree[1].it[1].dp[0][1]), min(tree[1].it[1].dp[1][0], tree[1].it[1].dp[1][1]));
}
int cat(int v) {
st[v] = 1;
solve(v, 0, inf);
return getans();
}
int dog(int v) {
st[v] = 2;
solve(v, inf, 0);
return getans();
}
int neighbor(int v){
if(st[v] == 0) return getans();
if(st[v] == 1) solve(v, 0, -inf);
if(st[v] == 2) solve(v, -inf, 0);
st[v] = 0;
return getans();
}
