#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 = 15;
ll n;
vector<pair<ll,ll>> ari;
bool is[MAXN][MAXN];
ll color[MAXN];
bool vis[MAXN];
vector<ll> adj[MAXN];
ll res;
pair<ll,ll> act;
void dfs(ll nd, ll p){
vis[nd]=true;
if(color[nd]==1) act.fst++;
if(color[nd]==2) act.snd++;
for(auto i:adj[nd])if(i!=p && is[nd][i]){
dfs(i,nd);
}
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
mset(is,false);
n = N;
forn(i,0,n-1){
A[i]--;
B[i]--;
ari.pb({A[i],B[i]});
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
is[A[i]][B[i]]=is[B[i]][A[i]]=true;
}
}
void solve(){
res=1000000;
forn(i,0,1<<(n-1)){
mset(vis,false);
ll cnt = 0;
forn(j,0,n-1){
if(i&(1<<j)){
cnt++;
is[ari[j].fst][ari[j].snd]=false;
is[ari[j].snd][ari[j].fst]=false;
}
}
bool yes = true;
forn(i,0,n) if(!vis[i]){act={0,0}; dfs(i,-1); if(act.fst!=0 && act.snd!=0) yes=false;}
if(yes) res=min(res,cnt);
forn(j,0,n-1){
if(i&(1<<j)){
is[ari[j].snd][ari[j].fst]=true;
is[ari[j].fst][ari[j].snd]=true;
}
}
}
}
int cat(int v) { v--;
color[v]=1;
solve();
return res;
}
int dog(int v) { v--;
color[v]=2;
solve();
return res;
}
int neighbor(int v) { v--;
color[v]=0;
solve();
return res;
}
