#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int N, Q;
vector<int> adj[100005];
int parent[100005];
int type_pet[100005]; // 0 = none, 1 = cat, 2 = dog
int dp[100005][2];
void predfs(int node, int par) {
parent[node] = par;
for (int x : adj[node]) if (x != par) {
predfs(x, node);
}
}
void dfs(int node, int par) {
dp[node][0] = dp[node][1] = 0;
for (int x : adj[node]) if (x != par) {
dfs(x, node);
dp[node][0] += min(dp[x][0], dp[x][1] + 1);
dp[node][1] += min(dp[x][1], dp[x][0] + 1);
}
if (type_pet[node] == 1) dp[node][1] = INF;
if (type_pet[node] == 2) dp[node][0] = INF;
}
void recalc_up(int node) {
while (node) {
dp[node][0] = dp[node][1] = 0;
for (int x : adj[node]) if (x != parent[node]) {
dp[node][0] += min(dp[x][0], dp[x][1] + 1);
dp[node][1] += min(dp[x][1], dp[x][0] + 1);
}
if (type_pet[node] == 1) dp[node][1] = INF;
if (type_pet[node] == 2) dp[node][0] = INF;
node = parent[node];
}
}
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].push_back(v);
adj[v].push_back(u);
}
predfs(1, 0);
dfs(1, 0);
}
int cat(int v) {
type_pet[v] = 1;
recalc_up(v);
return min(dp[1][0], dp[1][1]);
}
int dog(int v) {
type_pet[v] = 2;
recalc_up(v);
return min(dp[1][0], dp[1][1]);
}
int neighbor(int v) {
type_pet[v] = 0;
recalc_up(v);
return min(dp[1][0], dp[1][1]);
}
