#include "catdog.h"
#include <vector>
using namespace std;
const int MX = 1005;
int ada[MX], dp[MX][2];
vector<int> adj[MX];
void dfs(int nw, int bf){
dp[nw][0] = dp[nw][1] = 0;
for(int nx : adj[nw]) if(nx != bf){
dfs(nx, nw);
dp[nw][0] += min(dp[nx][0], dp[nx][1] + 1);
dp[nw][1] += min(dp[nx][1], dp[nx][0] + 1);
}
if(ada[nw] != -1)
dp[nw][1 - ada[nw]] = MX * MX;
}
void initialize(int N, vector<int> A, vector<int> B){
for(int i = 1; i < N; i ++){
adj[A[i - 1]].push_back(B[i - 1]);
adj[B[i - 1]].push_back(A[i - 1]);
}
for(int i = 1; i <= N; i ++)
ada[i] = -1;
}
int cat(int v){
ada[v] = 1;
dfs(1, 1);
return min(dp[1][0], dp[1][1]);
}
int dog(int v){
ada[v] = 0;
dfs(1, 1);
return min(dp[1][0], dp[1][1]);
}
int neighbor(int v){
ada[v] = -1;
dfs(1, 1);
return min(dp[1][0], dp[1][1]);
}
