#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+29;
ll n,a[N],cntc[N],cntd[N],m,dp[N][4];
vector<ll>g[N];
void dfs(ll v,ll pr=0){
dp[v][2]=dp[v][1]=0;
dp[v][3^a[v]]=1e9;
for(ll to:g[v]){
if(to==pr)continue;
dfs(to,v);
dp[v][1]+=min(dp[to][1],dp[to][2]+1);
dp[v][2]+=min(dp[to][2],dp[to][1]+1);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
m=A.size();
n=N;
for(ll i=1;i<=n;i++)a[i]=4;
for(ll i=0;i<m;i++){
ll u=A[i];
ll v=B[i];
assert(u>0&&u<=n);
assert(v>0&&v<=n);
g[v].push_back(u);
g[u].push_back(v);
}
}
ll calc(){
dfs(1);
return min(dp[1][1],dp[1][2]);
}
int cat(int v) {
a[v]=1;
return calc();
}
int dog(int v) {
a[v]=2;
return calc();
}
int neighbor(int v) {
ll x=a[v];
a[v]=3;
return calc();
}
