#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN=1e5, INF=1e9;
int n, type[mxN], dp[mxN][2];
vector<int> adj[mxN];
void initialize(int N, vector<int> A, vector<int> B) {
n=N;
for (int i=0; i<n-1; ++i) {
int u=A[i]-1, v=B[i]-1;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void dfs(int u=0, int p=-1) {
dp[u][0]=type[u]!=2?0:INF;
dp[u][1]=type[u]!=1?0:INF;
for (int v : adj[u])
if (v!=p) {
dfs(v, u);
for (int i : {0, 1})
dp[u][i]=min(min(dp[u][i]+dp[v][i], dp[u][i]+dp[v][i^1]+1), INF);
}
}
int solve() {
dfs();
return min(dp[0][0], dp[0][1]);
}
int cat(int v) {
type[v-1]=1;
return solve();
}
int dog(int v) {
type[v-1]=2;
return solve();
}
int neighbor(int v) {
type[v-1]=0;
return solve();
}
