#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; }