#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1.1e5;
int N;
vector<int> adj[MAXN];
int A[MAXN];
void initialize(int n, std::vector<int> a, std::vector<int> b) {
N = n;
for (int i = 0; i < N-1; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
for (int i = 1; i <= N; i++) {
A[i] = 2;
}
}
int query();
int cat(int v) {
A[v] = 0;
return query();
}
int dog(int v) {
A[v] = 1;
return query();
}
int neighbor(int v) {
A[v] = 2;
return query();
}
array<int, 2> dfs(int cur, int prv) {
array<int, 2> best = {0,0};
for (int nxt : adj[cur]) {
if (nxt == prv) continue;
auto nxtbest = dfs(nxt, cur);
for (int i = 0; i < 2; i++) best[i] += nxtbest[i];
}
if (A[cur] == 2) {
for (int i = 0; i < 2; i++) best[i] = min(best[i], 1 + best[1-i]);
} else {
best[1-A[cur]] = 1 + best[A[cur]];
}
return best;
}
int query() {
auto res = dfs(1, 0);
return min(res[0], res[1]);
}
