#include "catdog.h"
#include <bits/stdc++.h>
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b;i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
const int MAXN = 2000+5;
ll dp[MAXN][5];
vector<ll> adj[MAXN];
ll color[MAXN];
ll n;
ll f(ll x, ll y, ll p){
ll &res = dp[x][y];
if(res!=-1) return res;
if(color[x]!=0 && color[x]!=y) return 1000000000;
res=0;
for(auto i:adj[x]) if(i!=p){
res+=min(f(i,1+(y%2),x)+1,f(i,y,x));
}
//cout<<x<<" "<<y<<" "<<color[x]<<" "<<p<<" ----------> "<<res<<'\n';
return res;
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
n = N;
forn(i,0,n-1){
A[i]--;
B[i]--;
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
}
mset(color,0);
}
int cat(int v) { v--;
color[v]=1;
mset(dp,-1);
return min(f(0,1,-1),f(0,2,-1));
}
int dog(int v) { v--;
color[v]=2;
mset(dp,-1);
return min(f(0,1,-1),f(0,2,-1));
}
int neighbor(int v) { v--;
color[v]=0;
mset(dp,-1);
return min(f(0,1,-1),f(0,2,-1));
}
