#include "catdog.h"
#include<stdio.h>
#include<algorithm>
#define N 2000
int shin[N],dp[N][2], e[N][2],ne,h[N];
void link(int u,int v)
{
e[++ne][0]=v,e[ne][1]=h[u],h[u]=ne;
}
void dfs(int u,int p)
{
dp[u][0]=dp[u][1]=0;
for(int v,j=h[u];j;j=e[j][1])if((v=e[j][0])-p)
{
dfs(v,u);
for(int k=0;k<2;++k)
dp[u][k]+=std::min(dp[v][k],dp[v][k^1]+1);
}
if(shin[u])
{
dp[u][(shin[u]-1)^1]=1e9;
}
}
void initialize(int n, std::vector<int> a, std::vector<int> b)
{
for (int i=0;i<n-1;++i)link(a[i],b[i]),link(b[i],a[i]);
}
int cat(int u) {
shin[u]=1;
dfs(1,1);
return std::min(dp[1][0],dp[1][1]);
}
int dog(int u) {
shin[u]=2;
dfs(1,1);
return std::min(dp[1][0],dp[1][1]);
}
int neighbor(int u) {
shin[u]=0;
dfs(1,1);
return std::min(dp[1][0],dp[1][1]);
}
