#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int N = (int) 1e5 + 7;
const int INF = (int) 1e9 + 7;
int n;
int kitty[N];
int doge[N];
int cost_kitty[N];
int cost_doge[N];
vector<int> g[N];
void build(int a, int p = -1) {
vector<int> kids;
for (auto &b : g[a]) {
if (b != p) {
kids.push_back(b);
build(b, a);
}
}
g[a] = kids;
}
void dfs(int a) {
kitty[a] = cost_kitty[a];
doge[a] = cost_doge[a];
for (auto &b : g[a]) {
dfs(b);
kitty[a] += min(kitty[b], 1 + doge[b]);
doge[a] += min(doge[b], 1 + kitty[b]);
}
}
void initialize(int nn, std::vector<int> edgesA, std::vector<int> edgesB) {
n = nn;
for (int i = 0; i < n - 1; i++) {
int a = edgesA[i];
int b = edgesB[i];
g[a].push_back(b);
g[b].push_back(a);
}
build(1);
}
int cat(int v) {
cost_kitty[v] = INF;
cost_doge[v] = 0;
dfs(1);
return min(kitty[1], doge[1]);
}
int dog(int v) {
cost_kitty[v] = 0;
cost_doge[v] = INF;
dfs(1);
return min(kitty[1], doge[1]);
}
int neighbor(int v) {
cost_kitty[v] = 0;
cost_doge[v] = 0;
dfs(1);
return min(kitty[1], doge[1]);
}
