#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
#include "catdog.h"
int x;
vector<int> adj[100001];
int dp[100001][2];
int it[100001];
int n;
void initialize(int nn, std::vector<int> aa, std::vector<int> bb) {
n=nn;
for(int i=0;i<n-1;i++){
adj[aa[i]-1].pb(bb[i]-1);
adj[bb[i]-1].pb(aa[i]-1);
}
for(int i=0;i<n;i++){
it[i]=0;
}
}
void dfs(int no,int par=-1){
dp[no][0]=0;
dp[no][1]=0;
if(it[no]==1){
dp[no][1]=1e9;
}
else if(it[no]==2){
dp[no][0]=1e9;
}
for(auto j:adj[no]){
if(j!=par){
dfs(j,no);
dp[no][0]+=min(dp[j][0],dp[j][1]+1);
dp[no][1]+=min(dp[j][1],dp[j][0]+1);
}
}
}
int cat(int i) {
it[i-1]=1;
dfs(0);
return min(dp[0][0],dp[0][1]);
}
int dog(int i) {
it[i-1]=2;
dfs(0);
return min(dp[0][0],dp[0][1]);
}
int neighbor(int i) {
it[i-1]=0;
dfs(0);
return min(dp[0][0],dp[0][1]);
}
