#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
int n;
vector<int> g[N];
int dp[N][3];
int c[N];
void initialize(int _n, vector<int> a, vector<int> b){
n = _n;
for (int i = 1; i < n; i++){
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
}
void dfs(int x, int p){
dp[x][1]=0;
dp[x][2]=0;
for(auto i:g[x]){
if(i!=p){
dfs(i,x);
dp[x][1]+=min(dp[i][1],dp[i][2]+1);
dp[x][2]+=min(dp[i][2],dp[i][1]+1);
}
}
if(c[x]==1)dp[x][2]=1e9;
if(c[x]==2)dp[x][1]=1e9;
}
int cat(int v){
c[v]=1;
dfs(1,1);
return min(dp[1][1],dp[1][2]);
}
int dog(int v){
c[v]=2;
dfs(1,1);
return min(dp[1][1],dp[1][2]);
}
int neighbor(int v){
c[v]=0;
dfs(1,1);
return min(dp[1][1],dp[1][2]);
}
