#include "catdog.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std;
const int N=20;
int n,a[N];
bool b[N][N],vis[N];
pair<int,int> e[N];
vector<int> adj[N];
bool dfs(int node){
if (a[node]==2) return 0;
vis[node]=true;
bool ans=true;
for (auto u:adj[node]){
if (vis[u] || b[u][node]) continue;
ans&=dfs(u);
}return ans;
}
int getans(){
int ans=n;
for (int i=0;i<(1<<(n-1));i++){
int g=__popcount(i);
for (int j=0;j<n-1;j++) b[e[j].F][e[j].S]=b[e[j].S][e[j].F]=bool(i&(1<<j));
memset(vis,0,sizeof(vis));
for (int j=1;j<=n;j++){
if (a[j]!=1 || vis[j]) continue;
bool x=dfs(j);
if (!x) g=n;
}ans=min(ans,g);
}return ans;
}
void initialize(int NN, std::vector<int> A, std::vector<int> B) {
n=NN;
for (int i=0;i<n-1;i++){
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
e[i]={A[i],B[i]};
}return;
}
int cat(int v){
a[v]=1;
return getans();
}
int dog(int v) {
a[v]=2;
return getans();
}
int neighbor(int v) {
a[v]=0;
return getans();
}
