#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 1e5 + 7, inf = 1e9;
int n, par[N], head[N], chain[N], pos[N], sz[N], dp[N][2][2], st[N];
vector <int> edge[N];
void dfs(int u, int p){
dp[u][0][0] = dp[u][0][1] = dp[u][1][0] = 0;
if(st[u] == 1){
dp[u][0][1] = inf;
dp[u][0][0] = 1;
}
else if(st[u] == 2){
dp[u][1][0] = inf;
dp[u][0][0] = 1;
}
for(int v : edge[u]){
if(v == p) continue;
par[v] = u;
dfs(v, u);
dp[u][0][0] += min(dp[v][0][0], min(dp[v][1][0], dp[v][0][1]) + 1);
dp[u][1][0] += min(dp[v][1][0], min(dp[v][0][0], dp[v][0][1] + 1));
dp[u][0][1] += min(dp[v][0][1], min(dp[v][0][0], dp[v][1][0] + 1));
}
}
void initialize(int p, vector<int> A, vector<int> B){
n = p;
for(int i = 0; i < n - 1; i++){
edge[A[i]].pb(B[i]);
edge[B[i]].pb(A[i]);
}
dfs(1, 1);
}
int getans(){
return min(dp[1][0][0], min(dp[1][0][1], dp[1][1][0]));
}
int cat(int v) {
st[v] = 1;
dfs(1, 1);
return getans();
}
int dog(int v) {
st[v] = 2;
dfs(1, 1);
return getans();
}
int neighbor(int v) {
st[v] = 0;
dfs(1, 1);
return getans();
}
