#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e5;
int n;
int a[100005];
vector<int> con[100005];
int parent[100005];
int dp[100005][2];
void dfs(int nod)
{
for(int adj:con[nod])
{
if(adj==parent[nod])
continue;
parent[adj] = nod;
dfs(adj);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B)
{
n=N;
for(int i=1;i<=N;i++)
a[i]=2;
for(int i=0;i<n-1;i++)
{
con[A[i]].push_back(B[i]);
con[B[i]].push_back(A[i]);
}
dfs(1);
}
void calcdp(int nod)
{
dp[nod][0] = dp[nod][1] = 0;
for(int adj:con[nod])
{
if(adj==parent[nod])
continue;
calcdp(adj);
dp[nod][0] += dp[adj][0];
dp[nod][1] += dp[adj][1];
}
if(a[nod]==2)
{
dp[nod][0] = min(dp[nod][0], dp[nod][1] + 1);
dp[nod][1] = min(dp[nod][1], dp[nod][0] + 1);
}
else if(a[nod]==0)
{
dp[nod][1] = dp[nod][0] + 1;
}
else if(a[nod]==1)
{
dp[nod][0] = dp[nod][1] + 1;
}
//cerr<<nod<<" "<<dp[nod][0]<<" "<<dp[nod][1]<<" dp\n";
}
int cat(int v)
{
a[v] = 0;
calcdp(1);
return min(dp[1][0], dp[1][1]);
}
int dog(int v)
{
a[v] = 1;
calcdp(1);
return min(dp[1][0], dp[1][1]);
}
int neighbor(int v)
{
a[v] = 2;
calcdp(1);
return min(dp[1][0], dp[1][1]);
}
/*
5
1 2
2 3
2 4
4 5
2
1 3
2 5
*/
