#include "catdog.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using ll = long long;
#define debug(x) #x << " = " << x < '\n'
const int INF = 1e9;
const int MAXN = 1e5;
int dp[MAXN][3];
int type[MAXN];
std::vector<int> g[MAXN];
void dfs(int u, int p) {
if (p != u) {
g[u].erase(std::find(g[u].begin(), g[u].end(), p));
}
for (int v : g[u]) {
dfs(v, u);
}
}
void dfsDP(int u) {
dp[u][0] = dp[u][1] = dp[u][2] = +INF;
dp[u][type[u]] = 0;
for (int v : g[u]) {
dfsDP(v);
int nw[3] = {+INF, +INF, +INF};
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
nw[x] = std::min(nw[x], dp[u][x] + dp[v][y] + 1);
if ((x | y) != 3) {
nw[x | y] = std::min(nw[x | y], dp[u][x] + dp[v][y]);
}
}
}
dp[u][0] = nw[0];
dp[u][1] = nw[1];
dp[u][2] = nw[2];
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
for (int i = 0; i + 1 < N; i++) {
A[i]--, B[i]--;
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
dfs(0, 0);
}
int getAnswer() {
dfsDP(0);
return std::min({dp[0][0], dp[0][1], dp[0][2]});
}
int cat(int v) {
v--;
type[v] = 1;
return getAnswer();
}
int dog(int v) {
v--;
type[v] = 2;
return getAnswer();
}
int neighbor(int v) {
v--;
type[v] = 0;
return getAnswer();
}
