#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXN = 1e5 + 5;
int N;
vector<int> adj[MAXN];
int dp[MAXN][3];
int state[MAXN];
void DfsInit(int u, int p) {
if (p) {
adj[u].erase(find(begin(adj[u]), end(adj[u]), p));
}
for (auto v : adj[u]) {
DfsInit(v, u);
}
}
void DfsDp(int u) {
dp[u][0] = dp[u][1] = dp[u][2] = 0;
for (auto v : adj[u]) {
DfsDp(v);
dp[u][0] += min({dp[v][0], dp[v][1] + 1, dp[v][2] + 1});
dp[u][1] += min({dp[v][0], dp[v][1] + 0, dp[v][2] + 1});
dp[u][2] += min({dp[v][0], dp[v][1] + 1, dp[v][2] + 0});
}
if (state[u] != 0) {
dp[u][state[u]] = min(dp[u][state[u]], dp[u][0]);
dp[u][0] = dp[u][state[u] ^ 3] = INF;
}
}
int Solve() {
DfsDp(1);
return min({dp[1][0], dp[1][1], dp[1][2]});
}
void initialize(int N, vector<int> A, vector<int> B) {
::N = N;
for (int i = 0; i + 1 < N; i++) {
adj[A[i]].emplace_back(B[i]);
adj[B[i]].emplace_back(A[i]);
}
DfsInit(1, 0);
}
int cat(int v) {
state[v] = 1;
return Solve();
}
int dog(int v) {
state[v] = 2;
return Solve();
}
int neighbor(int v) {
state[v] = 0;
return Solve();
}
