#include <iostream>
#include <vector>
#include <algorithm>
#define fi first
#define se second
using namespace std;
using ll = long long;
ll inf = 1'000'000'000;
int n;
int idx;
vector<int> G,nxt,top,A;
void add_edge(int x,int y)
{
idx++;
G[idx]=y;
nxt[idx]=top[x];
top[x]=idx;
}
void initialize(int _n,vector<int> a,vector<int> b)
{
n=_n;
G=nxt=vector<int>(2*n+1);
top=A=vector<int>(n+1);
for(int i=1;i<=n-1;i++)
{
add_edge(a[i-1],b[i-1]);
add_edge(b[i-1],a[i-1]);
}
}
pair<ll,ll> dfs(int x,int tata)
{
pair<int,int> ans;
ans={0,0};
for(int i=top[x];i;i=nxt[i])
{
int y=G[i];
if(y==tata)
continue;
auto [cs,ds]=dfs(y,x);
ans.fi+=min(cs,ds+1);
ans.se+=min(ds,cs+1);
}
if(A[x]==1)
ans.se=inf;
if(A[x]==2)
ans.fi=inf;
return ans;
}
int cat(int x)
{
A[x]=1;
auto [c,d]=dfs(1,0);
return min(c,d);
}
int dog(int x)
{
A[x]=2;
auto [c,d]=dfs(1,0);
return min(c,d);
}
int neighbor(int x)
{
A[x]=0;
auto [c,d]=dfs(1,0);
return min(c,d);
}
