#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
int N, sz[MAX], head[MAX], par[MAX], heavy[MAX], pos[MAX], sz_chain[MAX], t[MAX];
vector<int> adj[MAX];
struct node
{
int a[2][2];
node()
{
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
a[i][j] = MAX;
}
friend node operator+(const node &a, const node &b)
{
node c;
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)
c.a[i][l] = min(c.a[i][l], a.a[i][j] + b.a[k][l] + (k != j));
return c;
}
};
struct segment_tree
{
vector<node> st;
segment_tree(int n) : st(n << 2) {}
segment_tree() : st(0) {}
void update(int id, int l, int r, int pos, int v_cat, int v_dog)
{
if (l == r)
{
st[id].a[0][0] += v_cat;
st[id].a[1][1] += v_dog;
}
else
{
int mid = l + r >> 1;
if (pos <= mid)
update(id << 1, l, mid, pos, v_cat, v_dog);
else
update(id << 1 | 1, mid + 1, r, pos, v_cat, v_dog);
st[id] = st[id << 1] + st[id << 1 | 1];
}
}
void build(int id, int l, int r)
{
if (l == r)
{
st[id].a[0][0] = 0;
st[id].a[1][1] = 0;
st[id].a[0][1] = MAX;
st[id].a[1][0] = MAX;
}
else
{
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
}
node get()
{
return st[1];
}
} chains[MAX];
void dfs_sz(int u)
{
sz[u] = 1;
for (int v : adj[u])
{
adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
par[v] = u;
dfs_sz(v);
sz[u] += sz[v];
if (sz[heavy[u]] < sz[v])
heavy[u] = v;
}
}
void dfs_hld(int u, int hd)
{
head[u] = hd;
pos[u] = ++sz_chain[hd];
if (heavy[u])
{
dfs_hld(heavy[u], hd);
for (int v : adj[u])
if (v != heavy[u])
dfs_hld(v, v);
}
}
void initialize(int N, vector<int> A, vector<int> B)
{
::N = N;
for (int i = 0; i < N - 1; ++i)
{
int u = A[i], v = B[i];
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
dfs_sz(1);
dfs_hld(1, 1);
for (int i = 1; i <= N; ++i)
{
if (head[i] == i)
{
chains[i] = segment_tree(sz_chain[i]);
chains[i].build(1, 1, sz_chain[i]);
}
}
}
void modify(int u, int cat, int dog)
{
while (u > 0)
{
node cur = chains[head[u]].get();
int fcat = min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
int fdog = min({cur.a[1][0], cur.a[1][1], cur.a[0][0] + 1, cur.a[0][1] + 1});
chains[head[u]].update(1, 1, sz_chain[head[u]], pos[u], cat, dog);
cur = chains[head[u]].get();
int gcat = min({cur.a[0][0], cur.a[0][1], cur.a[1][0] + 1, cur.a[1][1] + 1});
int gdog = min({cur.a[1][0], cur.a[1][1], cur.a[0][0] + 1, cur.a[0][1] + 1});
cat = gcat - fcat;
dog = gdog - fdog;
u = par[head[u]];
}
}
int answer()
{
node cur = chains[1].get();
int cat = min(cur.a[0][0], cur.a[0][1]);
int dog = min(cur.a[1][0], cur.a[1][1]);
return min(cat, dog);
}
int cat(int u)
{
modify(u, 0, MAX);
t[u] = 1;
return answer();
}
int dog(int u)
{
modify(u, MAX, 0);
t[u] = 2;
return answer();
}
int neighbor(int u)
{
if (t[u] == 1)
modify(u, 0, -MAX);
if (t[u] == 2)
modify(u, -MAX, 0);
t[u] = 0;
return answer();
}
