#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;
struct Info {
int dp[3];
void init() {
dp[0] = dp[1] = dp[2] = +INF;
}
void makeType(int x) {
init();
dp[x] = 0;
}
Info operator + (const Info &other) const {
Info ret;
ret.init();
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
ret.dp[x] = std::min(ret.dp[x], dp[x] + other.dp[y] + 1);
if ((x | y) != 3) {
ret.dp[x | y] = std::min(ret.dp[x | y], dp[x] + other.dp[y]);
}
}
}
return ret;
};
};
Info dp[MAXN];
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].makeType(type[u]);
for (int v : g[u]) {
dfsDP(v);
dp[u] = dp[u] + dp[v];
}
}
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].dp[0], dp[0].dp[1], dp[0].dp[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();
}
