#include "catdog.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int N = 111111;
int n;
vi adj[N];
int alien[N];
int dp[N][3];
const int INF = int(1e9);
void dfs(int u, int p=-1)
{
dp[u][0]=dp[u][1]=dp[u][2]=INF;
if(alien[u]==0) dp[u][0]=0;
if(alien[u]==0||alien[u]==1) dp[u][1]=0;
if(alien[u]==0||alien[u]==2) dp[u][2]=0;
for(int v:adj[u])
{
if(v==p) continue;
dfs(v,u);
if(alien[u]==0)
{
dp[u][0]+=min(dp[v][0],min(dp[v][1]+1,dp[v][2]+1));
}
if(alien[u]==0||alien[u]==1)
{
dp[u][1]+=min(dp[v][0],min(dp[v][1],dp[v][2]+1));
}
if(alien[u]==0||alien[u]==2)
{
dp[u][2]+=min(dp[v][0],min(dp[v][1]+1,dp[v][2]));
}
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B)
{
n=N;
for(int i=0;i<N-1;i++)
{
adj[A[i]-1].pb(B[i]-1); adj[B[i]-1].pb(A[i]-1);
}
dfs(0);
memset(alien,0,sizeof(alien));
}
int cat(int v)
{
v--; alien[v]=1;
dfs(0);
return min(dp[0][0],min(dp[0][1],dp[0][2]));
}
int dog(int v)
{
v--; alien[v]=2;
dfs(0);
return min(dp[0][0],min(dp[0][1],dp[0][2]));
}
int neighbor(int v)
{
v--; alien[v]=0;
dfs(0);
return min(dp[0][0],min(dp[0][1],dp[0][2]));
}
