#include <bits/stdc++.h>
#include "catdog.h"
#define pb emplace_back
#define ll long long
#define fi first
#define se second
#define mp make_pair
//#define int int64_t
using namespace std;
const int N = (int)1e5 + 2;
const int inf = 2e5;
int n, u, v, q, sz[N], cur[N], par[N], t, tail[N];
int cnt, cntp, head[N], pos[N], id[N], big[N];
vector<int> adj[N];
int l[N << 2], h[N << 2];
struct TNode {
int g[2][2];
TNode() {g[0][0] = g[1][1] = 0, g[1][0] = g[0][1] = inf;}
TNode operator +(const TNode& r)const& {
TNode res;
res.g[0][0] = min({g[0][1] + r.g[1][0], g[0][1] + r.g[0][0] + 1, g[0][0] + r.g[0][0], g[0][0] + r.g[1][0] + 1, inf});
res.g[0][1] = min({g[0][1] + r.g[1][1], g[0][1] + r.g[0][1] + 1, g[0][0] + r.g[0][1], g[0][0] + r.g[1][1] + 1, inf});
res.g[1][0] = min({g[1][1] + r.g[1][0], g[1][1] + r.g[0][0] + 1, g[1][0] + r.g[0][0], g[1][0] + r.g[1][0] + 1, inf});
res.g[1][1] = min({g[1][1] + r.g[1][1], g[1][1] + r.g[0][1] + 1, g[1][0] + r.g[0][1], g[1][0] + r.g[1][1] + 1, inf});
return res;
}
} st[N << 2], val;
void build(int x, int low, int high) {
l[x] = low, h[x] = high;
if(low == high) return;
int mid = (low + high) >> 1;
build(x << 1, low, mid);
build(x << 1 | 1, mid + 1, high);
}
void upd(int x, int pos, int add0, int add1) {
if(l[x] > pos || h[x] < pos) return;
if(l[x] == pos && h[x] == pos) {
st[x].g[0][0] += add0;
st[x].g[1][1] += add1;
return;
}
upd(x << 1, pos, add0, add1);
upd(x << 1 | 1, pos, add0, add1);
st[x] = st[x << 1] + st[x << 1 | 1];
}
TNode get(int x, int low, int high) {
if(low > high) return TNode();
if(low > h[x] || l[x] > high) return TNode();
if(low <= l[x] && h[x] <= high) return st[x];
return get(x << 1, low, high) + get(x << 1 | 1, low, high);
}
void hld(int u) {
if(!head[cnt]) head[cnt] = u;
id[u] = cnt, pos[u] = ++cntp, tail[cnt] = u;
for(int v: adj[u])
if(!big[u] || sz[v] > sz[big[u]]) big[u] = v;
if(big[u]) hld(big[u]);
for(int v: adj[u])
if(big[u] != v) ++cnt, hld(v);
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for(int i = 0; i < A.size(); ++i) {
adj[A[i]].pb(B[i]), adj[B[i]].pb(A[i]);
}
function<void(int)> dfs = [&](int u) {
sz[u] = 1;
for(int& v: adj[u]) {
if(v == par[u]) swap(v, adj[u].back());
if(v == par[u]) continue;
par[v] = u;
dfs(v);
sz[u] += sz[v];
}
if(par[u]) adj[u].pop_back();
};
dfs(1), cnt = 1, hld(1);
build(1, 1, n);
fill(cur, cur + n + 1, -1);
}
int f0, f1, top, nf0, nf1;
pair<int, int> getf(int l, int r) {
val = get(1, pos[l], pos[r]);
return mp(min({val.g[0][0], val.g[0][1], val.g[1][0] + 1, val.g[1][1] + 1}),
min({val.g[1][0], val.g[1][1], val.g[0][0] + 1, val.g[0][1] + 1}));
}
void update(int v, int add0, int add1) {
while(1) {
top = head[id[v]];
tie(f0, f1) = getf(top, tail[id[v]]);
upd(1, pos[v], add0, add1);
tie(nf0, nf1) = getf(top, tail[id[v]]);
if(top == 1) return;
add0 = nf0 - f0, add1 = nf1 - f1, v = par[top];
}
}
int getans() {
tie(f0, f1) = getf(1, tail[1]);
return min(f0, f1);
}
int cat(int v) {
cur[v] = 0;
update(v, 0, inf);
return getans();
}
int dog(int v) {
cur[v] = 1;
update(v, inf, 0);
return getans();
}
int neighbor(int v) {
if(cur[v] == 1) update(v, -inf, 0);
else if(cur[v] == 0) update(v, 0, -inf);
cur[v] = -1;
return getans();
}
