// 15:59
#include "bits/stdc++.h"
#include "catdog.h"
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int inf = int(1E9);
using M = std::array<std::array<i64, 2>, 2>;
M operator* (const M lhs, const M rhs) {
M res;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
res[i][j] = std::min({lhs[i][0] + rhs[0][j],
lhs[i][0] + rhs[1][j] + 1,
lhs[i][1] + rhs[0][j] + 1,
lhs[i][1] + rhs[1][j]});
}
}
return res;
}
M operator+ (const M lhs, const M rhs) {
M res {};
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
res[i][j] = lhs[i][j] + rhs[i][j];
}
}
return res;
}
M operator*= (M& lhs, const M rhs) {
return lhs = lhs * rhs;
}
M operator+= (M& lhs, const M rhs) {
return lhs = lhs + rhs;
}
M operator- (const M x) {
M res;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
res[i][j] = -x[i][j];
}
}
return res;
}
#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l) << 1)
struct segtree {
int n;
std::vector<M> tree;
void init(int n_) {
n = n_;
tree.resize(n << 1);
auto dfs = [&](auto&& self, int v, int l, int r) -> void {
if (l + 1 == r) {
tree[v][0][0] = tree[v][1][1] = 0;
tree[v][0][1] = tree[v][1][0] = inf;
debug(v, tree[v]);
return;
}
def;
self(self, lv, l, mid);
self(self, rv, mid, r);
tree[v] = tree[lv] * tree[rv];
};
dfs(dfs, 0, 0, n);
}
void add(int v, int l, int r, int p, M x) {
if (l + 1 == r) {
tree[v] += x;
debug(l, v, tree[v]);
return;
}
def;
if (p < mid) {
add(lv, l, mid, p, x);
} else {
add(rv, mid, r, p, x);
}
tree[v] = tree[lv] * tree[rv];
}
void add(int p, M x) {
add(0, 0, n, p, x);
}
M get(int v, int l, int r, int ql, int qr) {
if (ql == l && r == qr) {
return tree[v];
}
def;
if (qr <= mid) {
return get(lv, l, mid, ql, qr);
} else if (mid <= ql) {
return get(rv, mid, r, ql, qr);
} else {
return get(lv, l, mid, ql, mid)
* get(rv, mid, r, mid, qr);
}
}
M get(int l, int r) {
return get(0, 0, n, l, r);
}
} seg;
int N;
std::vector<std::vector<int>> adj;
int tim = 0;
std::vector<int> siz;
std::vector<int> par;
std::vector<int> top;
std::vector<int> tin;
std::vector<int> tout;
std::vector<int> len;
std::vector<int> typ;
void dfs1(int v) {
siz[v] = 1;
for (auto& u : adj[v]) {
adj[u].erase(std::find(adj[u].begin(), adj[u].end(), v));
par[u] = v;
dfs1(u);
siz[v] += siz[u];
if (siz[u] > siz[adj[v][0]]) {
std::swap(u, adj[v][0]);
}
}
}
void dfs2(int v) {
tin[v] = tim++;
for (auto u : adj[v]) {
if (u == adj[v][0]) {
top[u] = top[v];
len[top[v]] += 1;
} else {
top[u] = u;
len[u] = 1;
}
dfs2(u);
}
tout[v] = tim;
}
void build(int v) {
for (auto u : adj[v]) {
build(u);
if (top[u] == u) {
seg.add(tin[v], seg.get(tin[u], tin[u] + len[u]));
}
}
}
void debug_tree() {
auto dfs = [&](auto&& self, int v, int l, int r) -> void {
if (l + 1 == r) {
debug(l, r, seg.tree[v]);
return;
}
def;
self(self, lv, l, mid);
self(self, rv, mid, r);
};
dfs(dfs, 0, 0, N);
debug();
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
::N = N;
adj.resize(N);
seg.init(N);
siz.resize(N);
par.resize(N);
top.resize(N);
tin.resize(N);
tout.resize(N);
len.resize(N);
typ.resize(N);
for (int i = 0; i < N - 1; ++i) {
--A[i], --B[i];
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
dfs1(0);
len[0] = 1;
dfs2(0);
build(0);
// debug(tin);
// debug_tree();
}
void rem(int v) {
while (top[v]) {
v = top[v];
M x = seg.get(tin[v], tin[v] + len[v]);
M y {};
y[0][0] = std::min({x[0][0], x[0][1], x[1][0] + 1, x[1][1] + 1});
y[1][1] = std::min({x[1][0], x[1][1], x[0][0] + 1, x[0][1] + 1});
seg.add(tin[par[v]], -y);
v = par[v];
}
}
void add(int v) {
while (top[v]) {
v = top[v];
M x = seg.get(tin[v], tin[v] + len[v]);
M y {};
y[0][0] = std::min({x[0][0], x[0][1], x[1][0] + 1, x[1][1] + 1});
y[1][1] = std::min({x[1][0], x[1][1], x[0][0] + 1, x[0][1] + 1});
seg.add(tin[par[v]], y);
v = par[v];
}
}
int answer() {
// debug_tree();
M x = seg.get(0, len[0]);
i64 res = inf;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < 2; ++j) {
res = std::min(res, x[i][j]);
}
}
return res;
}
int cat(int v) {
--v;
// debug(__LINE__);
rem(v);
// debug(__LINE__);
// debug_tree();
// debug(__LINE__);
M x {};
typ[v] = 1;
x[1][1] = inf;
seg.add(tin[v], x);
add(v);
return answer();
}
int dog(int v) {
--v;
rem(v);
M x {};
typ[v] = 2;
x[0][0] = inf;
seg.add(tin[v], x);
add(v);
return answer();
}
int neighbor(int v) {
--v;
rem(v);
if (typ[v] == 1) {
M x {};
x[1][1] = -inf;
seg.add(tin[v], x);
} else {
M x {};
x[0][0] = -inf;
seg.add(tin[v], x);
}
typ[v] = 0;
add(v);
return answer();
}
