#include "catdog.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n;
vector<int> q[200100];
int dp[200100][3];
int a[200100];
void dfs(int v, int p){
dp[v][1] = dp[v][2] = 0;
if(a[v] == 2) dp[v][1] = 1e9;
if(a[v] == 1) dp[v][2] = 1e9;
for(int to: q[v]){
if(to == p) continue;
dfs(to, v);
dp[v][1] += min(dp[to][1], dp[to][2] + 1);
dp[v][2] += min(dp[to][1] + 1, dp[to][2]);
}
}
void initialize(int N, vector<int> A, vector<int> B) {
n = N;
for(int i=0; i<A.size(); i++){
int l = A[i];
int r = B[i];
q[l].pb(r);
q[r].pb(l);
}
}
int cat(int v) {
a[v] = 1;
dfs(1, 0);
return min(dp[1][1], dp[1][2]);
}
int dog(int v) {
a[v] = 2;
dfs(1, 0);
return min(dp[1][1], dp[1][2]);
}
int neighbor(int v) {
a[v] = 0;
dfs(1, 0);
return min(dp[1][1], dp[1][2]);
}
