#include<bits/stdc++.h>
#include "catdog.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()
int N;
vvi adj; vi col;
int dfs(int u, int p, int mask){
int ans = col[u];
for(auto v : adj[u]){
if(v == p) continue;
if(mask&(1<<v)){
if(dfs(v, u, mask) == 3)
return 3;
}else ans |= dfs(v, u, mask);
}
return ans;
}
int calc(){
int ans = INF;
for(int mask = 0; mask < (1<<N); mask++){
if(dfs(0, 0, mask) != 3)
ans = min(ans, __builtin_popcount(mask));
}
return ans;
}
void initialize(int n, vi a, vi b){
N = n; adj = vvi(n); col = vi(n);
for(int x = 0; x < n-1; x++){
adj[a[x]-1].push_back(b[x]-1);
adj[b[x]-1].push_back(a[x]-1);
}
return;
}
// cat ==> 1
int cat(int v){
v--; col[v] = 1;
return calc();
}
// dog ==> 2
int dog(int v){
v--; col[v] = 2;
return calc();
}
// neighbor ==> 0
int neighbor(int v){
v--; col[v] = 0;
return calc();
}
