#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
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 nbest = dfs(nxt, cur);
best[0] += min(nbest[0], nbest[1]+1);
best[1] += min(nbest[1], nbest[0]+1);
}
if (A[cur] == 0) {
best[0] = INF;
} else if (A[cur] == 1) {
best[1] = INF;
}
return best;
}
int query() {
auto res = dfs(1, 0);
return min(res[0], res[1]);
}
