#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
int A[100009], D[2][100009];
vector<int> adj[100009], tree[100009];
void dfs(int x, int p) {
for(auto& it: adj[x]) {
if(it != p) {
tree[x].push_back(it);
dfs(it, x);
}
}
}
void initialize(int N, vector<int> A, vector<int> B) {
for(int i=0; i<N-1; i++) {
int u = A[i], v = B[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1);
}
void go(int x) {
for(auto& it: tree[x]) go(it);
if(A[x] == 0) {
int s1 = 0, s2 = 0;
for(auto& it: tree[x]) {
if(A[it] == 0) {
s1 += D[0][it];
s2 += D[1][it];
}
if(A[it] == 1) {
s1 += D[0][it];
s2 += D[0][it] + 1;
}
if(A[it] == 2) {
s1 += D[1][it] + 1;
s2 += D[1][it];
}
}
D[0][x] = s1;
D[1][x] = s2;
}
if(A[x] == 1) {
int s = 0;
for(auto& it: tree[x]) s += min(D[0][it], D[1][it] + 1);
D[0][x] = s;
D[1][x] = 1e9;
}
if(A[x] == 2) {
int s = 0;
for(auto& it: tree[x]) s += min(D[0][it] + 1, D[1][it]);
D[0][x] = 1e9;
D[1][x] = s;
}
}
int DP() {
go(1);
return min(D[0][1], D[1][1]);
}
int cat(int v) {
A[v] = 1;
return DP();
}
int dog(int v) {
A[v] = 2;
return DP();
}
int neighbor(int v) {
A[v] = 0;
return DP();
}
