#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 no_cat[N];
int no_dog[N];
vector<int> g[N];
int type[N];
/**
nothing = 0
cat = 1
dog = 2
**/
void dfs(int a, int p = -1) {
if (type[a] == 0) {
no_cat[a] = no_dog[a] = 0;
for (auto &b : g[a]) {
if (b == p) {
continue;
}
dfs(b, a);
no_cat[a] += min(no_cat[b], 1 + no_dog[b]);
no_dog[a] += min(no_dog[b], 1 + no_cat[b]);
}
return;
}
if (type[a] == 1) {
no_cat[a] = INF;
no_dog[a] = 0;
for (auto &b : g[a]) {
if (b == p) {
continue;
}
dfs(b, a);
no_dog[a] += min(no_dog[b], 1 + no_cat[b]);
}
return;
}
if (type[a] == 2) {
no_cat[a] = 0;
no_dog[a] = INF;
for (auto &b : g[a]) {
if (b == p) {
continue;
}
dfs(b, a);
no_cat[a] += min(no_cat[b], 1 + no_dog[b]);
}
return;
}
assert(false);
}
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);
}
}
int cat(int v) {
type[v] = 1;
dfs(1);
return min(no_cat[1], no_dog[1]);
}
int dog(int v) {
type[v] = 2;
dfs(1);
return min(no_cat[1], no_dog[1]);
}
int neighbor(int v) {
type[v] = 0;
dfs(1);
return min(no_cat[1], no_dog[1]);
}
