#include "catdog.h"
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
typedef long long int lld;
int x;
vector<int> tree[1000000];
int animal[1000000];
int n;
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n=N;
vector<int>nei[N];
for(int i=0;i<N-1;i++){A[i]--;B[i]--;
nei[A[i]].push_back(B[i]);
nei[B[i]].push_back(A[i]);
}
queue<int>q;
int dist[n];
for(int i=0;i<n;i++){
dist[i]=-1;
}
dist[0]=0;
q.push(0);
dist[0]=0;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<nei[u].size();i++){
int v=nei[u][i];
if(dist[v]==-1){
dist[v]=dist[u]+1;
q.push(v);
}
}
}
for(int i=0;i<n-1;i++){
if(dist[A[i]]>dist[B[i]]){//cout<<B[i]<<" "<<A[i]<<endl;
tree[B[i]].push_back(A[i]);
}else{//cout<<A[i]<<" "<<B[i]<<endl;
tree[A[i]].push_back(B[i]);
}
}
for(int i=0;i<n;i++)animal[i]=0;
}
lld DP[1000000][3];
lld trabalha(int node,int territory){
if(DP[node][territory]!=-1)return DP[node][territory];
if(animal[node]>0 && territory!=animal[node])return 1000000000;
if(tree[node].size()==0){
DP[node][territory]=0;
return 0;
}
DP[node][territory]=0;
if(territory==1){
for(int i=0;i<tree[node].size();i++){int v=tree[node][i];
DP[node][territory]+=min(1+trabalha(v,0),min(trabalha(v,1),1+trabalha(v,2)));
}
}
if(territory==2){
for(int i=0;i<tree[node].size();i++){int v=tree[node][i];
DP[node][territory]+=min(1+trabalha(v,0),min(trabalha(v,2),1+trabalha(v,1)));
}
}
if(territory==0){
for(int i=0;i<tree[node].size();i++){int v=tree[node][i];
DP[node][territory]+=min(trabalha(v,0),min(1+trabalha(v,1),1+trabalha(v,2)));
}
}
return DP[node][territory];
}
int cat(int v) {v--;
animal[v]=1;
for(int i=0;i<n;i++){
DP[i][0]=-1;
DP[i][1]=-1;
DP[i][2]=-1;
}
//cout<<trabalha(0,1)<<endl;
return min(trabalha(0,0),min(trabalha(0,1),trabalha(0,2)));
}
int dog(int v) {v--;
animal[v]=2;
for(int i=0;i<n;i++){
DP[i][0]=-1;
DP[i][1]=-1;
DP[i][2]=-1;
}
return min(trabalha(0,0),min(trabalha(0,1),trabalha(0,2)));
}
int neighbor(int v){v--;
animal[v]=0;
for(int i=0;i<n;i++){
DP[i][0]=-1;
DP[i][1]=-1;
DP[i][2]=-1;
}
return min(trabalha(0,0),min(trabalha(0,1),trabalha(0,2)));
}
