#include<bits/stdc++.h>
//#define name "InvMOD"
#ifndef name
#include "catdog.h"
#endif // name
using namespace std;
template<typename T> bool ckmn(T& a, const T& b){
if(a > b)
return a = b, true;
return false;
}
const int N = 1e5 + 5;
int n, dp[2][N], a[N];
vector<int> adj[N];
// brute (cat: 0, dog: 1)
int calc_dp(int x, int p){
dp[0][x] = dp[1][x] = 0;
if(a[x] < 2) dp[a[x] ^ 1][x] = n;
for(int v : adj[x])if(v != p){
calc_dp(v, x);
dp[0][x] = dp[0][x] + min(dp[0][v], dp[1][v] + 1);
dp[1][x] = dp[1][x] + min(dp[1][v], dp[0][v] + 1);
ckmn(dp[0][x], n), ckmn(dp[1][x], n);
}
return min(dp[0][x], dp[1][x]);
}
void initialize(int _n, vector<int> u, vector<int> v){
n = _n;
for(int i = 0; i < n - 1; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
for(int i = 0; i < n; i++) a[i] = 2;
}
int cat(int v){
a[v] = 0;
return calc_dp(1, -1);
}
int dog(int v){
a[v] = 1;
return calc_dp(1, -1);
}
int neighbor(int v){
a[v] = 2;
return calc_dp(1, -1);
}
