#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
using tri = array<int, 3>;
const int N = 1e5 + 5;
const int inf = 1e9 + 5;
int n;
int state[N];
tri dp[N];
vi g[N];
void chkmin(int& x, int y) {
x = min(x, y);
}
tri merge(tri a, tri b) {
tri ret = {inf, inf, inf};
for(int i : {0,1,2}) for(int j : {0,1,2}) {
chkmin(ret[i], a[i]+b[j]+1);
if((i|j) != 3) chkmin(ret[i|j], a[i]+b[j]);
}
return ret;
}
void solve(int u, int dad = 0) {
for(int v : g[u]) if(v != dad) {
solve(v, u);
}
dp[u] = {inf, inf, inf};
dp[u][state[u]] = 0;
for(int v : g[u]) if(v != dad) {
dp[u] = merge(dp[u], dp[v]);
}
}
void initialize(int _n, std::vector<int> A, std::vector<int> B) {
n = _n;
for(int i = 0; i < sz(A); ++i) {
g[A[i]].emplace_back(B[i]);
g[B[i]].emplace_back(A[i]);
}
}
int cat(int v) {
state[v] = 1;
solve(1);
return *min_element(all(dp[1]));
}
int dog(int v) {
state[v] = 2;
solve(1);
return *min_element(all(dp[1]));
}
int neighbor(int v) {
state[v] = 0;
solve(1);
return *min_element(all(dp[1]));
}
