#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
vector<int>adj[maxn];
int val[maxn],n,inf=1e6+5;
void pre(int u,int par=0){
int j=-1;
for(int i=0;i<(int)adj[u].size();i++){
if(adj[u][i]!=par){
pre(adj[u][i],u);
}
else{
j=i;
}
}
if(j>=0){
adj[u].erase(adj[u].begin()+j);
}
return ;
}
pair<int,int>cal(int u){
vector<pair<int,int>>ret;
for(auto x:adj[u]){
ret.push_back(cal(x));
}
int red=0,blue=0;
for(int i=0;i<(int)ret.size();i++){
red+=min(ret[i].first,ret[i].second+1);
blue+=min(ret[i].first+1,ret[i].second);
}
if(val[u]==0){
return make_pair(min(red,blue+1),min(blue,red+1));
}
else if(val[u]==1){
return make_pair(red,red+1);
}
else{
return make_pair(blue+1,blue);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n=N;
for(int i=0;i<n-1;i++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
pre(1);
}
int cat(int v) {
val[v]=1;
pair<int,int>res=cal(1);
return min(res.first,res.second);
}
int dog(int v) {
val[v]=2;
pair<int,int>res=cal(1);
return min(res.first,res.second);
}
int neighbor(int v) {
val[v]=0;
pair<int,int>res=cal(1);
return min(res.first,res.second);
}
