#include "catdog.h"
#include<vector>
#include<algorithm>
using namespace std;
int w[1010], n, D[1010][3], par[1010];
vector<int>E[1010], Ch[1010];
void DFS(int a, int pp) {
par[a] = pp;
for (auto &x : E[a]) {
if (x == pp)continue;
DFS(x, a);
Ch[a].push_back(x);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
int i;
for (i = 0; i < n - 1; i++) {
E[A[i]].push_back(B[i]);
E[B[i]].push_back(A[i]);
}
DFS(1, 0);
}
void UDT(int a) {
if (w[a] == 0) {
int s1 = 0, s2 = 0;
for (auto &x : Ch[a]) {
s1 += D[x][1];
s2 += D[x][2];
}
D[a][1] = min(s1, s2 + 1);
D[a][2] = min(s2, s1 + 1);
}
if (w[a] == 1) {
int s = 0;
for (auto &x : Ch[a]) {
s += D[x][1];
}
D[a][1] = s;
D[a][2] = s + 1;
}
if (w[a] == 2) {
int s = 0;
for (auto &x : Ch[a]) {
s += D[x][2];
}
D[a][1] = s + 1;
D[a][2] = s;
}
}
int cat(int v) {
w[v] = 1;
while (v) {
UDT(v);
v = par[v];
}
return min(D[1][1], D[1][2]);
}
int dog(int v) {
w[v] = 2;
while (v) {
UDT(v);
v = par[v];
}
return min(D[1][1], D[1][2]);
}
int neighbor(int v) {
w[v] = 0;
while (v) {
UDT(v);
v = par[v];
}
return min(D[1][1], D[1][2]);
}
