#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 2;
const int inf = 1e9;
int n,state[maxn];
int dp[maxn][3];
vector<int> a[maxn];
void dfs(int u, int pa = -1) {
dp[u][1] = dp[u][2] = 0;
if (state[u]==1) dp[u][2] = inf;
if (state[u]==2) dp[u][1] = inf;
for (int v : a[u]) if (v!=pa) {
dfs(v,u);
if (state[u] == 1) {
dp[u][1] += min(dp[v][1], dp[v][2] + 1);
}
else if (state[u] == 2) {
dp[u][2] += min(dp[v][2], dp[v][1] + 1);
}
else {
dp[u][1] += min(dp[v][1], dp[v][2] + 1);
dp[u][2] += min(dp[v][2], dp[v][1] + 1);
}
}
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for (int i = 0; i < N-1; i++) {
a[A[i]].push_back(B[i]);
a[B[i]].push_back(A[i]);
}
}
int cat(int v) {
state[v] = 1;
dfs(1);
return min(dp[1][1], dp[1][2]);
}
int dog(int v) {
state[v] = 2;
dfs(1);
return min(dp[1][1], dp[1][2]);;
}
int neighbor(int v) {
state[v] = 0;
dfs(1);
return min(dp[1][1], dp[1][2]);;
}
