#include <bits/stdc++.h>
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
const int inf = 1e6;
const int N = 1e5 + 5;
struct node {
int dp[2][2];
node(int a = inf, int b = inf, int c = inf, int d = inf) {
dp[0][0] = a;
dp[0][1] = b;
dp[1][0] = c;
dp[1][1] = d;
}
node operator + (const node& o) const {
node res;
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) {
res.dp[i][j] = min(res.dp[i][j], dp[i][k] + o.dp[l][j] + (k != l));
}
}
}
}
return res;
}
int ans() {
return min({dp[0][0], dp[0][1], dp[1][0], dp[1][1]});
}
};
node base[] = {
node(0, inf, inf, 0),
node(0, inf, inf, inf),
node(inf, inf, inf, 0)
};
struct SEG {
vector<node> it;
int n;
SEG(int _n = 0) {
n = _n;
it.assign(4 * n + 5, node());
}
void build(int k, int l, int r) {
if(l == r) {
it[k] = base[0];
return;
}
int mid = l + r >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
it[k] = it[k << 1] + it[k << 1 | 1];
}
void update(int pos, node val) {
int l = 1, r = n, k = 1;
while(l < r) {
int mid = l + r >> 1;
if(pos <= mid) {
k = (k << 1);
r = mid;
} else {
k = (k << 1 | 1);
l = mid + 1;
}
}
it[k] = val;
while(k) {
k >>= 1;
it[k] = it[k << 1] + it[k << 1 | 1];
}
}
};
int n;
vector<int> g[N];
int id[N], curId, pos[N], len[N], top[N], fa[N], sz[N];
int type[N];
int sumChild[2][N];
SEG tree[N];
void dfs(int u, int p) {
sz[u] = 1;
for(int v : g[u]) if(v != p) {
fa[v] = u;
dfs(v, u);
sz[u] += sz[v];
}
}
void hld(int u, int p) {
if(!id[u]) {
id[u] = ++curId;
top[curId] = u;
}
pos[u] = ++len[curId];
int hc = -1;
for(int v : g[u]) if(v != p) {
if(hc == -1 || sz[v] > sz[hc]) hc = v;
}
if(hc != -1) {
id[hc] = id[u];
hld(hc, u);
}
for(int v : g[u]) if(v != p && v != hc) {
hld(v, u);
}
}
void initialize(int _n, vector<int> A, vector<int> B) {
n = _n;
for(int i = 0; i < n - 1; ++i) {
g[A[i]].emplace_back(B[i]);
g[B[i]].emplace_back(A[i]);
}
dfs(1, 0);
hld(1, 0);
for(int i = 1; i <= n; ++i) {
if(i == top[id[i]]) {
tree[i] = SEG(len[id[i]]);
tree[i].build(1, 1, len[id[i]]);
}
}
}
void upd(int u) {
while(u > 0) {
int head = top[id[u]];
node c = tree[head].it[1];
int p = fa[head];
sumChild[0][p] -= min({c.dp[0][0], c.dp[0][1], c.dp[1][0] + 1, c.dp[1][1] + 1});
sumChild[1][p] -= min({c.dp[1][0], c.dp[1][1], c.dp[0][0] + 1, c.dp[0][1] + 1});
c = base[type[u]];
if(c.dp[0][0] != inf) c.dp[0][0] += sumChild[0][u];
if(c.dp[1][1] != inf) c.dp[1][1] += sumChild[1][u];
tree[head].update(pos[u], c);
c = tree[head].it[1];
sumChild[0][p] += min({c.dp[0][0], c.dp[0][1], c.dp[1][0] + 1, c.dp[1][1] + 1});
sumChild[1][p] += min({c.dp[1][0], c.dp[1][1], c.dp[0][0] + 1, c.dp[0][1] + 1});
u = p;
}
}
int cat(int x) {
type[x] = 1;
upd(x);
return tree[1].it[1].ans();
}
int dog(int x) {
type[x] = 2;
upd(x);
return tree[1].it[1].ans();
}
int neighbor(int x) {
type[x] = 0;
upd(x);
return tree[1].it[1].ans();
}
//int32_t main() {
// ios_base::sync_with_stdio(false);
// cin.tie(0), cout.tie(0);
//
// file("A") else file("task");
// int _n, _q;
// cin >> _n;
// vector<int> A(_n - 1), B(_n - 1);
// for(int i = 0; i < _n - 1; ++i) cin >> A[i] >> B[i];
// initialize(_n, A, B);
//
// cin >> _q;
// while(_q--) {
// int t, x;
// cin >> t >> x;
// if(t == 1) cout << cat(x) << '\n';
// if(t == 2) cout << dog(x) << '\n';
// if(t == 3) cout << neighbor(x) << '\n';
// }
// return 0;
//}
