#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+29;
ll n,a[N],cntc[N],cntd[N],m,dp[N][8],dp2[8],cnt[N][4];
vector<ll>g[N];
bool can(ll v,ll mask){
if(a[v]==4)return 1;
if((mask>>(3^a[v]))&1)return 1;
return 0;
}
void merge(ll v,ll u){
if((a[v]^a[u])==3){
for(ll mask=1;mask<=7;mask++){
dp2[mask]=1e18;
if(!((mask>>a[u])&1))continue;
dp2[mask]=dp[v][mask]+1+min({dp[u][0],dp[u][1],dp[u][2],dp[u][3],dp[u][4],dp[u][5],dp[u][6],dp[u][7]});
}
}else{
for(ll mask=0;mask<=7;mask++){
dp2[mask]=1e18;
if(can(v,mask)){
dp2[mask]=dp[v][mask]+1+min({dp[u][0],dp[u][1],dp[u][2],dp[u][3],dp[u][4],dp[u][5],dp[u][6],dp[u][7]});
if(!((mask>>a[u])&1))dp2[mask]=min(dp2[mask],dp[v][mask]+dp[u][mask]);
}
}
}for(ll mask=0;mask<=7;mask++)dp[v][mask]=dp2[mask];
}void dfs(ll v,ll pr=0){
for(ll mask=0;mask<=7;mask++){
dp[v][mask]=0;
}for(ll to:g[v]){
if(to==pr)continue;
dfs(to,v);
merge(v,to);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
m=A.size();
n=N;
for(ll i=1;i<=n;i++)a[i]=4;
for(ll i=0;i<m;i++){
ll u=A[i];
ll v=B[i];
assert(u>0&&u<=n);
assert(v>0&&v<=n);
g[v].push_back(u);
g[u].push_back(v);
}
}
ll calc(){
dfs(1);
return min({dp[1][0],dp[1][1],dp[1][2],dp[1][3],dp[1][4],dp[1][5],dp[1][6],dp[1][7]});
}
int cat(int v) {
a[v]=1;
return calc();
}
int dog(int v) {
a[v]=2;
return calc();
}
int neighbor(int v) {
ll x=a[v];
a[v]=4;
return calc();
}
